You can decrease a GIF's file size by choosing a palette with fewer colors, thus reducing its colour depth.
The instructions below are for Photoshop 5. Many other image editors will have similar procedures, and current versions of Photoshop will have more simplified procedures -- consult your software's help documentation.
To minimize your GIF's size in Photoshop 5:
Choose Indexed Color from Photoshop's Mode menu.
When asked what palette to use, choose Web and make sure Diffusion is set. (This will render your image's color palette equivalent to the one used by Netscape and Internet Explorer.)
If you are satisfied with the quality of this image, proceed to step #4. If not, follow the steps immediately below:
Choose Indexed Color from the Mode menu again.
When asked what palette to use, choose Adaptive and Diffusion.
Set the color depth to 4.
If you are satisfied with the quality of this image, proceed to step #4. If not, repeat the last four steps, setting the color depth to 5, 6 or more until image quality is satisfactory. (The larger the number, the larger your GIF will be.)
Now that the color depth has been minimised, choose RGB from the Mode menu.
Choose Indexed Color again to remove any excess colors from the palette.
Choose Export from the File menu and select GIF89.
If you do not want the image background to appear over textured pages, use the eyedropper to make the appropriate color transparent. See How do I make a transparent GIF? for further details.