Main Content
There sure are a lot of options under the "Save for Web and Devices" list. Which one is best? Spend some time reading about them on the web, and take a look at these examples.
JPEG
This is the most common image format in the world. Choose maximum quality every time, unless you REALLY need more disc space, or quicker downloads.
jpg, maximum quality

This is as good as you can get on the web.
jpeg, low quality

In the low quality version, parts seem blurred or like they have "cellulite". This is caused by the compression of the file, which clumps like colors together.
gif-256 colors

Gif files have a maximum of 256 colors, so each of the pixels is assigned one of these values. They don't look as good as jpegs, and often seem "speckled". Look just under the roof, in the red area, and you'll see the speckling more clearly.
gif-64 colors

You can really see the speckles in this.
gif-2 colors

The ultimate compression is achieved by converting the file to only two colors. In this case, a light and a dark brown.
png 8-256 colors

Png-8 is very similar to gif format. It still has a pallette of colors to choose from, but unlike gif, there are no legal issues with its use. The speckling still exists.
png-8 2 colors

Again, just like gif, you can compress a png to just 2 colors.
png-24

Png also makes high quality images without "speckles". This looks as good as a jpeg at 100 quality. But the file size is bigger. Hover over each file to look at its file size.
So why would we use anything except jpeg? Two reasons: animation and transparency.
Animated gif
Only gif supports animation. Okay, apng is another animation format, but it's not widely used. SWF files also animate, but photoshop doesn't export them. So we're stuck with gif.
This box is gray to illustrate how transparency works on the web.
Transparency-gif

This pig has been placed on a gray background, but you can see that the transparency leaves (in this case) a little bit of a white halo around the pig, and the colors are "speckled".
Transparency-png

You can see that the png looks better, both in terms of transparency and overall color continuity.
Transparency-jpg

Jpeg format does not support transparency.