Here are some results from various methods of image optimization:

high quality JPG: 88k

low quality JPG: 27k

16-color GIF: 72k

256-color GIF: 203k

low quality JPG: 21k

high quality JPG: 52k

web palette GIF: 15k

JPEG (Joint Photographic Experts Group)

• lossy (removes colors to save on file size—human eyes more sensitive to change of brightness than change of color)
• millions of colors
• variable quality (file size and quality have an inverse relationship)
• progressive download

GIF (Graphic Interchange Format)

• lossless (nothing removed from the original file)
• few colors (compresses by limiting the color palette)
• GIF87a (transparent)
• GIF 89a (animated)
• dither to reduce banding (best if used sparingly)
• interlaced

What does this all mean?

JPEG format is great for photographic images, while GIF format
is better for those that look "cartoony," or those that have a few
number of solid colors.
Use Photoshop's Save for Web & Devices... command to test which
optimization technique is best for your graphics.