For the highest quality, you need to use a vector art program like Adobe Illustrator. Applications like Photoshop and Gimp are raster-based, meaning when you draw your logo, it is represented by discrete pixels at a fixed resolution. For example, if you resize the image for print (higher resolution = higher DPI) the image will be blockier and not very crisp. Vector art is represented by geometric shapes/equations, so it's easy to transform these images without loss. The downside of vector art is that it's somewhat harder to draw and it's not usually photo realistic.
Inkscape is a free vector drawing app, but I haven't used it.