The Kalm Traveler can obviously be found in the town of Kalm located on the eastern continent. 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 that he is looking for: The Guide Book, the Desert Rose and the Earth Harp. In order 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) on 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. Click on the link below for more information:
The Earth Harp: Can be obtained by defeating Emerald Weapon. Click on the link below for more information:
The rewards that you receive for turning in all three items are included below.
Your first task is to obtain the Guide Book in order to obtain an Underwater Materia. Underwater Materia is pretty much 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). Ghost Ships can be morphed into a Guide Book using 
Morph Materia.
Note that Morph Materia typically reduces a character to 1/8 of a regular attack and that Morph has to be the last attack used to kill the Ghost Ship in order to turn it into an item. You can get around this by using Yuffie with her 
Conformer weapon as this weapon ignores the damage reducing 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 sections are included above).
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 in order to defeat Ruby Weapon. It is a very lacklustre prize, which means that defeating Ruby Weapon is really just for fun.
Transcendant Convoker
You will receive the Transcendent Convoker Trophy once you pick up the Master Summon Materia that drops on the ground.
