According to page 99 of the manual,
The palace is a special building. Part building, part wonder, the palace appears in the first city you build, which makes that city the capital of your empire. If your capital city is captured, your palace will be rebuilt in another city, making that city your new capital. If you subsequently retake your original capital, the palace will move back to its original location.
In the first game I played, I lost my capital pretty early on to raiders from a neighboring civ. Fortunately, I already had another city by that point, so my capital moved there and I got to stay in the game. About a dozen turns later, I liberated my original capital, but it didn't automatically become my civ's capital again. Nor did I see an option to build a Palace in its city production screen. The Palace building stayed in my second city, and the little capital star icon stayed in the second city's name banner, for the rest of the game.
I guess it doesn't really matter in the grand scheme of things, but I really wanted my original capital to stay the capital. Was there a way I could have made that happen? Or was it supposed to happen automatically and I discovered a bug?