Preparation
First off, make sure you registered the expansion (in the POL viewer where you manage your account). If you haven't put in the registration code, you don't get any ToA content. Then, make sure you have your Boarding Pass by doing in Lower Jeuno. Remember to wait the real-life hour between turning in the items and getting the pass (this will become a theme for the new jobs). If you want to, you can do the rest of the setup while you wait that hour.
Next, go to Bastok Markets and talk to Shamarhaan standing by the fountain. He's rather hard to miss, since he has a Puppet dancing in front of him. This must be done to set up the PUP quest. Now, while you are in Bastok, you will want to pick up some items for the BLU quest. Acquire a and a . Use those links if you need help finding them items in question. Finally, you need a . This can be acquired at the small boat in the Valkurm Dunes whenever there are certain weather effects, or purchased off of the Auction house.
Okay, so once you've got your Boarding Pass, flagged the PUP quest, and collecting your BLU quest items, get your butt to Mhuara and ride the ferry to Aht Urhgan.
Socializing
Once the ferry docks, I highly recommend purchasing the maps for this new area. They are sold by an NPC immediately across from where the ferry drops you off (sadly, some of the zones you have to travel to will not have their maps sold here). At the very least, get the town map.
Now, from where you bought the maps, head East and climb up a set of stairs. In the middle of this area you will see an NPC named Waoud, who will flag BLU for you. Talk to him, and he will ask you a series of questions. Generally, if you understand that BLU is a ruthless, aggressive, yet honorable warrior, almost akin to a monster itself, you will know how to answer everything correctly. If he takes 1000 gil, you got it wrong. If you talk to him again, and you did everything right, he should ask you to bring him a particular kind of treasure from the Middle Lands (the normal areas of FFXI).
In order to do the next part of the quest, you have to wait a real-life hour again. Oh boy. But rather than waste time, lets flag the COR quest. In the same section of town you are in, head south a bit (staying upstairs) and talk to Ratihb. He has two quests, mind you, so make sure you flag the one involving the small child. If you get the quest about the Mithran gambler, talk to him again for the other quest.
From where you currently are, head North and talk to Mafwahb who will be standing by the gate. This will initiate a cutscene, and is the second stage of the COR quest. Now, while we're in the area, we might as well start PUP. Up above you is an NPC named Iruki-Waraki. He's on the elevated wall, so you will have to climb a set of stairs to get to him. Talk to him, and he tells you he has no puppet. From there go West and then North. On the upper level of this zone you will find an Automaton Shop. Talk to Ghatsad, and he'll ask you to find an old automaton that was damaged.
So, now it's time to go talk to our friend Waoud again. You may have to zone out of town and back in, and you definitely have to wait one real-life hour. Talk to him again, and he reminds you to bring him the item. It will be one of the three items you collected before you left the Middle Lands, so you should already have it in your inventory. Trade it to him. He then reveals that he didn't want it for himself, and asks you to deliver it.
The Immortals
The next section of this journey will require Sneak and Invisible. If you have a subjob that can grant you the spells, take it. For now, you won't have to enter combat, so don't worry about your stats or your battle capacity. Zone west into Al Zahbi, and look on the city map. You should see an exit to Bhaflau Thickets. Take it. Once you zone out, Sneak/Invisible should be up. You will see a lighthouse on the map (and in the distance). Head for it. Enter the Cave at I-7. Enter the next area called Adeewa Subterenne. Keep your Sneak/Invisible up. Move through this zone and when you see a ledge where you can drop down (on the right), do so. Immediately following that, take the slope to your left. You'll go down considerably and wind up in a room with a glowing section fo floor. Walk to it, enjoy your cutscene, become a Blue Mage.
We're Gonna Need A Bigger Boat
Congratulations, you've unlocked Blue Mage. Sorry to say, that was the easy part. After the cutscene, you will wind up back in town. Head for Port Ephramad (on the map, near where you talked to the automaton maker) and take that ferry to Nashmau. Once you dock, you may want to look for a party, because you will come into contact with MOBs ranging from Easy Prey to Tough, even if you are L75. What's more, unless you have a high level THF in the party, you will have to kill a few of them for a key. You will also have to click on a ??? with quite a few MOBs around it. Sneak/Invis is mandatory, I'd recommend bringing two stacks of Oils and Powders for this next part.
Once you have your party (or, if you are a THF, your lockpicking tools), take the North exit out of Nashmau and zone into Caedarva Mire. You won't have the map but here's how to get where you are going. At first, the path only leads one way (south), so take it. Once you reach the first clearing, the really simple rule is to always go north, and if you can't go north, go east. Be warned: IMPS HAVE TRUE SIGHT. Do everything right and you'll wind up in another cave, this one called Arrapago Reef.
Arrapago Reef Sucks
Yes, seriously, it really does. The aggro in this zone, while not deadly on its own, is rather obnoxious. Follow the only path you can until you see the first boat. On that boat are some very aggresive MOBs. There is also a ??? underneath one of the sets of stairs on the boat, immediately to your right as you board the boat. That's the item you need for PUP, and your Invisible has to be DOWN to click on it. Really, that's not too bad, since you have to kill some of these MOBs in order to get a Lamian Fang Key anyway (unless you have a THF). Click on the ???, one way or another.
Once you have done that, and you are ready to open the door that's up ahead (because you either have the key or brought a THF), get back off of the boat using the second plank and head Northeast through the cave. Sneak/Invisible, of course, must be up. Shortly thereafter, you will come to an Iron Door on your left, likely guarded by a Bogey-style MOB. This door requires either the Lamian Fang Key or else a THF with tools. You have to drop Invisible to open it, but thankfully the undead MOB guarding it won't aggro you for that. Open the door and go up another plank onto a second ship. Near the back of the ship, around H-10, you will see a ???. Click it, get your cutscene for COR, and get the hell out of there. You're done in this zone, so head back to town.
One you are back in Nashmau, take the West exit out of town. Keep Sneak/Invisible up. Follow this path and you will come to a small graveyard. Northwest of the graveyard is another cave. Zone in. The good news is that there are no MOBs in this zone. Head left from the entrance, and click on the ??? on the rock. Once you view that cutscene, look to your left and you will see that the passageway continues. Follow it back into the cave and click on the large, black wall at the end of cave. This will trigger your last cutscene for COR and give you an item to use once COR hits level 5.
Homecoming
Get back to Nashmau. Get back to Aht Urghan. Return to the Galka that works on automatons (in the sama area as the ferry you ride back). Hand him the broken automaton and then be prepared to wait another real-life hour. Fun! Once he completes your automaton, head South and East and talk to the Tarutaru Puppetmaster from before. He will allow you to name your puppet, give you an item to control your puppet (which resides in your ranged attack slot) and unlock the final new job: PUP. Congratulations! Now return to the starting area of your city of choice and compete with the two hundred other people who just unlocked these jobs for rabbits.