All you have to do to switch nations in the present is pay some gil. The amount will vary depending on the nation's current rank in the Conquest tally. I know you can change to Windurst at Heaven's Tower, but I don't know where you would do it in Sandy or Bastok. I would think that it would be in the Chateau or the Metalworks.

To change your nation in the past, I think you just do the quest that would normally ally you with that nation.