You always have one (1 - count 'em, one) Palace. (This does not count the Forbidden Palace, which acts roughly like a second Palace.

)
The city your Palace is in is your Capital. If you build a Palace elsewhere, your Capital is shifted to that city.
Why would you want to move your Palace? The Palace is the *core* of your civilization. If it is on the coast, you lose all the nice city locations that are underwater. Same if it is a narrow isthmus. To get a productive core, you sometimes want to move your Palace to a new city.
A not too uncommon practice in plain Civ3 and in PTW is to build the Forbidden Palace right next to your Palace, and then *jump* your Palace to the other side of your civ (sometimes even on another continent!). This gives you a good "secondary core" around the FP, which keeps your old core productive, and also gives you a powerful new core where it can do the most good.
But unless you have a Great Leader to rush it, building a Palace takes a looooong time, so you have to plan it carefully.
Sometimes the Palace is moved because it is used as a "pre-build" for a Great Wonder, and then that Wonder is "stolen" by another Civ, or you forget you are pre-building, and all of a sudden, whoops!
