GIF, JPEG, or PNG?
If the image is a photograph or other type of continuous tone images, JPEG offers excellent compression with little degradation of the image's quality. Experiment with the compression until you arrive at the quality (and size) you'd like.
GIFs (debatably pronounced with a hard G), despite using a proprietary format, are supported by all browsers and are best used with images composed of solid colour blocks (like logos). To prevent the colours from dithering (becoming spotted), use the Web safe palette.
The graphic format PNG was designed specially for the Web, and offers a greater level of control over the image quality than both GIFs and JPEGs. Most browsers support PNGs natively, but Internet Explorer (on Windows) can’t use the format’s transparency features. To create a transparent graphic, use a GIF or try some proprietary tricks.