realneed4speed, when optimizing images for the web, there's always a tradeoff between small file sizes and image quality. Different people have different methods; here's how I do it.
In the Save for Web dialog, make sure you have the 4-up showing. Then in one of the windoids, show a gif, in another a jpeg. I usually start very low, in the case of a gif, depending on the image, with 4-8 colors. If that looks horrible, bump it up until it looks acceptable. Fool with dithering, too. You can also "lock" important colors. Often, dithering can dramatically save file size and make the image look better too. But then, sometimes not...each image is different.
Same thing with the jpeg. Start low, work your way up until the image is acceptable looking. Keep an eye on the file sizes as you work. Sometimes, a very slight blur helps, too.
In general, use jpeg for photographic images and gif for flat color, particularly if there's text.
There's no one answer that works for all images; thing to do is play around with the Save for Web dialog until you see the image you like, and an acceptable file size. Keep in mind your entire web page when looking at file sizes; a 30kb image may not seem large, unless you have ten of them on the same page!