NOTE: You must have completed mission Immortal Sentries to get the cutscene and approach all NPCs as a blue mage. In addition, if you are viewing the extra cutscene you get after completing the job quest for the first time ("You had no reason to return here..."), you have to wait till the next game day before being able to receive this quest.
Speak with Waoud and choose "Gaze away" to have him tell your fortune.
Zone and speak to Waoud again and choose "Gaze away" as before. During the cutscene that follows, choose "I have" and you will be told to visit the five original Staging Points. You must zone before speaking to Waoud for this cutscene; otherwise he'll just repeat the original Q&A used to unlock the blue mage job.
If you received the cut-scene after talking to Waoud the first time, you do not have to zone and talk to him again. If you do you will receive a little dialogue and end up paying him 1,000 gil.
Be sure not to talk to him before zoning or else you will have to go through the question-and-answer cutscene you did to first unlock blue mage, and then pay him 1,000 gil.
If you start down the question-and-answer path accidentally, you can disconnect/crash your client without fear of breaking the quest progression.
Visit each staging point and speak with the Immortal Sentry at each as Blue Mage. They will each give you a key item "Brand." If at any time you want to know what brands you've already acquired, you can go to Permanent Key items and check them off.