If you need to scale images up at the ratio you're describing, it's practically necessary to work with vector images rather than raster images. The main difference is that raster images are made up of pixels, discrete dots of a fixed size, whereas vector images are described by geometric paths.
The essential point is that vector images can be scaled up practically infinitely while retaining smooth edges, but scaling up a raster image increases the size of each individual pixel and produces "blocky" effects.
You can read more about the differences here:
http://en.wikipedia.org/wiki/Raster_graphics
http://en.wikipedia.org/wiki/Vector_graphics
Even though Photoshop is meant for working with photos, which by nature are raster images, it has a fairly decent set of vector tools. However, Illustrator is really the preferred tool for working with vector graphics, and probably the one you should be using. Fireworks provides a mix of both toolsets and may be less intimidating than Illustrator if you're just getting started.
One final note. If your final output is for the web, keep the vector file, but export a raster version (most likely a PNG), at the size needed for display on the site. This way you get the maximum quality output, since the vector to raster conversion is happening AT the size required and there is no scaling of the raster image after rasterization. You also preserve the vector file should you need to edit it later.
