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 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.
Note: 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.
Note: 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. 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.