It still seems to be a bit of a mystery as to which city inherits the palace -- usually seems to track the high-population cities, but others have clearly shown a lesser-pop city becoming the new capitol. But the palace appearence will occur right away -- it won't wait for the next city you build.
If you are attempting to use it in cultural battles, I think you need to focus on manual palace builds or GL-inspired rushed Palaces -- a palace relocation for "cultural warfare" comes at a steep price of losing the power and improvements of the current capitol city, especially if you cannot be certain as to where the new palace will spring up.
Knight-Dragon: Many people will disband their capitol city early in the game in order to position their capitol in a more strategically valued location - for example more centered in a land mass allowing for less corruption than say a coastal location would provide. I have only used it in the very early game -- if I know I am going to perform the "palace jump," I will build nothing but settlers, workers and military units in the city (so nothing is "lost" when the capitol is disbanded. I make sure my "taget capitol" is the largest town (probably by adding workers to the town) and make sure it has a temple, library or other cultural building completed. I disband the capitol by building a settler at 2 pop with no food surplus -- a pop-up comes asking do I want to disband and I answer "yes." The city disappears, a settler appears, and (hopefully) the palace jumps to the target city. The settler can then be used to rebuild the city in the original capitol's location. By employing this tactic, you are essentially (1) paying 30 shields and 2 pop-points for a new palace (settler), (2) foregoing building early improvements in the original capitol for some period of time, and (3) taking a chance on where your new palace will find a home -- the alternative is to manually build a new palace (much more than 30 shields, generate and use a GL for a palace relocation, or live with a less-than-perfect palace location.