After you just got the submarine, visit Kalm and head for the house in the lower right corner of the screen. Enter, go upstairs and talk to the old man. He will tell you about the journey he is going to make and that he needs three items to get going. Here are the descriptions how to get these items:
In the underwater reactor in Junon, you will encounter a "Ghost Ship" sometimes. You have to attack the "Ghost Ship" with the "Morph" command (you need to have the Morph command materia) until it changes into the Guidebook. In exchange for the Guidebook, you will get the Underwater materia, which will allow you to breathe underwater (which eliminates the 20 minutes time limit when fighting the Emerald Weapon).
You get the Earth Harp when you beat the Emerald Weapon. In exchange for the Earth Harp, the old man will give you all three Master Materia.
You get the Desert Rose when you beat the Ruby Weapon. In exchange for the Desert Rose, you receive a Golden Chocobo.