A note about color
The number of colors in an image is relatively important. More colors = more information; more information = bigger file size; conversely less colors = less information; less information = smaller file size. This may be obvious to some but is worth stating. Simply speaking the more colors you have in an image, the more information you need in order to display that image. So if we are going to try to optimize an image so as to take up as little disk space as possible, we need to see how few colors we can get away with and still have a decent looking image. With that in mind, the trick when converting from RGB to Indexed Color Mode is to use the fewest colors possible.

To get to the Indexed Color dialog box, select [Image], [Mode] and then [Indexed Color...].

As you can see in the image above, there are 3 controls here - Resolution, Palette, and Dither. We'll explain a little about each, below.

Resolution
Resolution in this dialog box refers to the number of colors you would like to retain in the image. Indexed color mode (and the GIF format) will only allow a maximum of 256 colors. You can specify exactly how many colors you want by selecting Other and typing in the exact number. The bits per pixel values that you can choose as radio buttons are as follows:

It is probably best to experiment with exact colors if you want to truly optimize your image.

Sometimes Photoshop will have the Other box in the Resolution section already filled in if your original RGB image has 256 or less colors. If this is true, you should also notice the Exact button in the Palette section is automatically selected. This means that there will be no loss in color when you finish converting your image.

I've heard that a move of 1 bit per pixel less will make your images about 1/8 smaller, but I haven't tried testing that to confirm it. Your best bet is really trial and error. If it doesn't look good, Photoshop will let you undo with the click of a mouse (Command-z for a quick keyboard shortcut) and then you can try a different setting. Experiment and see how you like the results because they will be different for every image.

Below are some images that I converted to indexed color mode. The first one is 3-bit (7K), the second is 5-bit (11K), and the third is 8-bit (20K).

The middle image is perfectly acceptable and saves us almost half of the file size of the larger image. It would probably be best to experiment and see if we could squeeze more out of the image by saving it at 4-bit. If we were really trying to optimize, I would then experiment with actual values next to the Other button. This lets me save it at the exact optimum color level to balance size and quality.

There is one caveat and that is that once you convert your image to Indexed Color and save, you can't go back to the original number of colors. This fact makes it very important to save the same image in RGB mode under a different name before you start editing so that you can always go back to an original.

Palette
Adaptive is usually going to be the best choice for most images and it's the one Photoshop will choose automatically if it is converting from a large color palette. Exact will be chosen if your image started out with less than 256 colors. Exact will convert the color palette exactly, without any loss of colors.

Dither
Dithering is the adjustment of adjacent pixels of different colors to give the illusion of a third color. It gives you the illusion that there are more colors than really are present. Diffusion and None are usually the only options. Diffusion is best used for photographic type images and None for simple illustrations with simple areas of color. Trial and error is going to be the ticket here for each image you come across.