When you talk to the ships captain, there will be a dialog option to travel to any zones where you’ve unlocked the foothold. (If it says quest, it may mean that you’re on the foothold quest for that zone.)
[quote=“Cloudy-silvermoon, post:11, topic:1240112”]
Also, does this have to be done on both Horde and Alliance? So if I have done it on Horde already… does it count for Alliance?
[/quote]If you’ve already unlocked world quests on another character (on either faction) then you should be able to go right to Uniting Kul Tiras without doing the footholds.
It’s still not a terrible idea to do at least one of them so you can actually get to the other continent. You will also still have to do them if you want to do the War Campaign. (But you don’t need the War Campaign to unlock Naz’jatar or Mechagon.)
I should also note that if you did the Mechagon achievement on Horde-side and want to unlock the Mechagnomes, you can talk to Gila Crosswires in the Stormwind Embassy for the Mechagon starter quest that lets you skip Naz’jatar.