It's easy to do.
Load your image.
Then go to Image-> Mode -> Indexed Color
Now here are some interesting options
The first few terms should be easy enough to get, they make palettes specifically for mac or windows or web etc.
The latter terms need a little explaining...
local is used for single images, master for multiple images.
Perceptual - is used for colors the eye has greater sensitivity towards.
Selective - is broader and focuses more on web colors.
Adaptive - creates a sample from most used colors in the photo.
Custom - well lets you customize the table and Previous lets you switch to a previous palette.
Colors - is how many colors you want in your palette, 256 is max.
Forced - ensures certain colors like Black and White, Primaries (red, green, blue, cyan, magenta, yellow, black, and white), Web (The full 216 colors) or Custom colors are added to the palette.
Transparency - This either creates a special transparency index or you can choose how you will fill the transparency, with white or your chosen color.
Matte - The transparency color foreground, background etc, also affects how smooth the transition between transparent and non transparent pixels will be.
Not using a matte creates hard transparency.
Dither - used to simulate colors not in the color table. Not using dithering creates the next closet color often creating hard transitions. You can use Preserve Exact Colors to protect colors from dithering. Noise is good for preserving edges.
Amount - how much to dither, may increase file size.
Now choose the best options for you photo. This will create a color table you can get to now.
Go to Image -> Mode -> Color Table to enable you to see, alter and export your table.
For directions on that see here.
Now it's important to note, the quality of a photo heavily impacts your color output as someone has suggested.
Compare these two images as far as color tables goes. One has been scaled and edited incorrectly resulting in interpolating between the colors, while the other image is set perfectly.
You can tell how perfectly colors are setup if you get this screen.