No. The palace is always built and upgraded at your capital.
Once the build/upgrade is complete, you locate a free plot on an island, click on it and choose "colonise". You must also have an additional 1200 wood, 40 spare citizens and X amount of gold. Can't remember exactly how much gold though.
Once the build/upgrade is complete, you locate a free plot on an island, click on it and choose "colonise". You must also have an additional 1200 wood, 40 spare citizens and X amount of gold. Can't remember exactly how much gold though.