A bit of background first. When dealing with web graphics, an image will ultimately be in one of two color modes. One is RGB Color, and the other is Indexed Color. RGB images can theoretically contain over 16 million colors, making them suitable for photographs etc, and are usually saved in JPEG format for the web. Indexed color mode gives you a maximum of 256 colors to work with, and are usually saved in GIF format for the web. As you point out, other formats, such as .bmp, can also handle these color modes.
So how does this affect file size? Well, for RGB, every pixel needs 3 bytes to store the color. You could think of it as 1 byte each for Red, Green & Blue. Indexed color, however, only uses 1 byte per pixel, so it will always end up a third of the size of RGB.
However, all this is based on uncompressed images. On the web, all the popular formats are compressed to speed up download times. In the case of indexed color images, reducing the amount of colors can help in a number of ways.
Firstly, there is a color table associated with the image which is basically an index of the 256 colors being used. If this table is reduced to 100 entries, the file size is slightly reduced.
Secondly, and more importantly, when an image is converted to Indexed Color mode, there are some colors that are practically identical, but are being dealt with as unique entries. An area of seemingly flat color can actually contain a subtle amount of 'noise' which can hinder compression techniques. Reducing the amount of colors effectively reduces some of the noise, and in turn makes the image easier to compress.
Obviously there is a lot more to compression than this, but hopefully this long rambling post has been of some help!