You can find the Kalm Traveler in the town of Kalm, located on the eastern continent (seems fairly obvious!). Use the map and the screenshot below to help you find it:

He is located in the house furthest to the right on the second floor. Speak to him, and he will tell you that he is going on a journey to pray for his friend’s souls. He will then give you a riddle that reads as follows:

“A map that was sunk along with the ship.
……… ‘Guidebook’
A rose that blooms once every 1000 years
in the desert.
……… ‘Desert Rose’
A harp that soothes those who hear it
……… ‘Earth Harp’”

These are the three items he is looking for: The Guide Book, the Desert Rose, and the Earth Harp. To obtain all three items as part of the last side quest in the game, you have to defeat both Emerald Weapon and Ruby Weapon (detailed in other sections of this guide).

The Guide Book: Details for obtaining the Guide Book are included below. You can trade a Guide Book for an Underwater Materia, which removes a timer (with a time limit) for the battle against Emerald Weapon. Without the Underwater Materia you are limited to 20:00 minutes.

The Desert Rose: Can be obtained by defeating Ruby Weapon. Use the link below for more information:

The Earth Harp: Can be obtained by defeating Emerald Weapon. Use the link below for more information:

The rewards you receive for turning in all three items are included below.

Obtaining the Guide Book / Underwater Materia

Your first task is to obtain the Guide Book to obtain an Underwater Materia. Underwater Materia is a requirement for completing the Emerald Weapon boss fight, as the 20:00 minute timer that starts at the beginning of the battle is difficult to beat.

Travel to Junon and back to the road that leads to the Underwater Reactor.

You need to fight an enemy called a Ghost Ship (shown in the screenshot below), and you can find them in the tube area just before the reactor (also shown in the screenshot below). You can morph Ghost Ships into a Guide Book using Morph Materia.

Note that Morph Materia typically reduces a character to ¹⁄₈ of a regular attack and that Morph has to be the last attack used to kill the Ghost Ship to turn it into an item. You can get around this by using Yuffie with her Conformer weapon, as this weapon ignores the damage reduction, making it much easier to morph a Ghost Ship.

Return to the town of Kalm and speak to the Kalm Traveler. He will offer to trade you an Underwater Materia for the Guide Book.

This is all you can do with the Kalm Traveler side quest for now. The remaining parts involve defeating Emerald Weapon and Ruby Weapon (links to those side quest pages is included above).

Earth Harp and Desert Rose

The reward for defeating Emerald Weapon (the easier of the two fights) and obtaining the Earth Harp is three Master Materia: Master Command Materia, Master Magic Materia, and Master Summon Materia.

The reward for defeating Ruby Weapon and obtaining the Desert Rose is just a Gold Chocobo, which you will have already obtained to defeat Ruby Weapon. It is a very lackluster prize, which means that defeating Ruby Weapon is really just for fun.