How can I make my logo suitable for all purposes, from webpages to very large printed banners?
I currently use use Photoshop.
e100's advice is spot on. A vector application such as Illustrator is the best tool for logo design, whether you start on paper and scan it in, or work directly within the program.
This isn't the whole story, however. Scalability doesn't just involve vectors; the detail in a logo must also be adjusted for the size of the finished artwork. Just as with text, fine detail will either get lost or appear too fussy at small sizes, and a logo that is drawn to look good at business card size will tend to appear stolid or clunky at very large sizes.
This is a bit tricky to demo on a low-resolution device like a monitor, but I'll try to convey the idea.
Here's a logo for a riverside community non-profit:
The wavy lines read well at this size, but look what happens when we bring it down to a business card:
You see the problem immediately: those fine lines are all but invisible. In print, you run a very strong chance that ink spread will swallow them completely. The solution is to make a version for small sizes with less detail, but that conveys the same impression:
In this case, increasing the text weight to bold is also necessary, because it is a subtly crafted serif face (Trajan) with fine detail that disappears at tiny sizes.
There is an excellent example of this in John McWade's "Before and After Graphics for Business." There is an entire section of the book devoted to logo design, and this is one of the books I recommend frequently for this and its other content.
The answer is to create your logo artwork as vector rather than raster graphics. You can then use this artwork directly for print work, or export raster artwork at the size you need for web graphics.
While Photoshop has some vector support, if you have Creative Suite, Illustrator is the tool for the job. If you don't, then Inkscape (which is free) is worth looking at.
In addition to Adobe Illustrator which is clearly the gold-standard of commercial vector graphics tools, you should give some consideration to Inkscape. Inkscape is a vector drawing tool that would be an excellent chose for building scalable logo art. Inkscape is also free and runs on lots of platforms including both Windows and Mac.
The key attribute of these tools is that they operate in an abstract representation of shapes and lines rather than on a field of pixels. When using the resulting artwork, it is only converted to pixels near the end of the process. This allows the art have sharp features at all scales.
Note that this advantage holds from billboard scale down to the printed page. However at very small scales (small in the sense that the rendered image would span only a few tens of pixels, as in an icon) it is often the case that a skilled artist will need to refine the art to make the best possible use of the limited number of available pixels.
I use Photoshop to create logo's, if you use the correct tools within Photoshop I don't see any problem - you can create vectors so you would be able to scale them no problem. You can obviously use Illustrator as others have suggested, but just use what you're comfortable with.
@Scott I think you were a bit blunt with your comment as you gave no constructive ideas as to what to use instead and why Photoshop is so wrong?
With Photoshop you can't just create something and save it in a vector format and be good to go, but all I'm saying is you can create a logo that will be scalable, using the Pen tool and text (so long as you don't make it bold using Photoshop when the actual font didn't come with a bold option etc). I'm sure there are other ways, I just prefer to draw things from scratch with the Pen tool :)