What do you need to do to get portals to each of Hyjal, Vashir, Deepholm and Uldum

It is designed so that after you visited a zone for the first time, using a quest chain that leads there, you will be able to return to the zone via portal. However, this sometimes bugs. Especially the portal to Hyjal does not appear for many people until they did the quest chain leading to Twilight Highlands.

edit: Yesterday's hotfix

The Orgrimmar portal to Mount Hyjal should now appear for players who flew directly into Hyjal to start questing, rather than take the Moonglade portal.

I have found that you need to get the Pre-Quests for the zones and to actually travel there by following these quests. Once you have entered Hyjal, Twilight Highlands, Vash etc the portals are open.