The new palace goes to the best city. The best city is determined by the formula that lists the top five cities in the world on the F11 screen. It is a mix of population, wonders, improvements. In most cases it is the city with the highest population of native citizens. However, sometimes a slightly smaller city can become capital if it has many more improvements and/or wonders.
Players can use this free palace jump. It is an excellent strategy for peninsula starts or coastal starts on a large land mass. Some players disband the capital (produce a settler at pop 2, with no extra food) very early in the game to get a more centralized location. Another trick is to build the Forbidden Palace right next to the original capital before disbanding. This is the most efficient way to get a Forbidden Palace without a great leader.
Be careful with the free palace jump. Make sure that the new capital-to-be is the best city by a wide margin., because a mistake on a palace jump can ruin a good game.