When a computer's graphics system uses 8 bits of information to store each pixel in an image, the most effective way of gaining the widest range of colors is to use a Color Look Up Table (CLUT). This is called indexed color. Each pixel can be one of 256 colors (2^8) and the colors are chosen from a palette of 16 million. If the palette is chosen carefully and the image doesn't have too wide a range of color, you can get a reasonably pleasing result.
The choice of palette, and what your operating system does to it, however can really mess up your images. Both the Mac OS and Windows have standard 256-color palettes (not the same colors of course). They are called the system palettes and were chosen to have the widest application possible.
Photoshop can create custom palettes for your images but beware that the system displaying your image may not have access to the custom palette.