You can complete the Cavern of the Stolen Fayth side quest during your first pass through the Calm Lands, however it is recommended that you come back once your characters are much higher leveled. Yojimbo will cost you 190,350 gil to obtain and you can easily get to the end of the game without acquiring him.
The Cavern of the Stolen Fayth is located at the Gorge Bottom just north of the Calm Lands. The easiest way to get there is to use the Airship to travel to Mt. Gagazet and then head south back in to the Calm Lands.
Save your game at the Save Sphere before you enter the cavern. Make sure to use your weapons with the 
Capture ability while you are down here if you have it to begin amassing the fiends that you need for the Monster Arena side quests.
The cave is fairly linear. Take the first pathway on the right that you come across to find a treasure chest that contains a 
Megalixir. Continue into the first main open area for a scene and some dialogue.
Lulu and Auron will explain that the Fayth in this area was stolen long ago. A thief stole this particular Aeon in an attempt to stop summoners from dying when they summon the Final Aeon.
You may encounter a Magic Urn while you are in the Cavern. You will receive an item from the Urn if you attack the correct eye. There is no way to know ahead of time which eye is the correct one - this is strictly a game of chance. The items are of limited value though so you may just want to use the 
Flee command and avoid fighting them altogether.
You can learn the “Doom” Ronso Rage ability by having him use Lancet on a Ghost enemy in this area. Check out the Overdrive section for more information on Kimahri’s Ronso Rage.
Take a right at the upcoming “T” intersection and you will find a treasure chest that contains a 
Lv. 2 Key Sphere. Going straight at the next intersection will lead to a treasure chest that contains a 
Fortune Sphere.
As you continue down the path you will find another treasure chest that contains two 
Mega-Potions and just off to the left side of the screen you will find 
Al Bhed Primer (Vol. XXV). Save your game at the Save Sphere near this area before you continue.
The next area leads to an encounter against an unsent summoner, Lady Ginnem. She is the summoner that Lulu was a guardian for. The summoner will initiate a battle against you and she will summon Yojimbo.
Yojimbo is not too difficult to defeat. You can use Yuna’s Aeons if you are having difficulty. He has approximately 30,000 HP.
Step on the teleportation platform in the middle of the room to enable it. Stand on the platform facing forward and press the 
Button to warp into the Chamber of the Fayth.
Here you will meet up with Yojimbo, the next Aeon that Yuna can learn to summon, however you will need to offer him a contract in order to have him join your party.
Yojimbo will present you with three options:
Choose the third option (“To defeat the most powerful of enemies”) as this will reduce the overall cost of Yojimbo in terms of gil. The price starts at 250,000 gil but you can haggle up to three times by offering Yojimbo less money. You must offer him at least 50% of what he is offering plus 1 to get him to lower his price.
He will then offer his lowest price of 190,350 gil which you should accept.
You now have Yojimbo as a new Aeon.
Before you leave you can use the teleported to warp into the room on the left and the right before warping to the entrance.
The room on the left contains a treasure chest with a 
Flexible Arm weapon for Rikku (which contains 4 empty customizable ability slots). The room on the right contains two treasure chests - one which contains an 
MP Sphere and one which contains two X-Potions.
Exit the Cavern of the Stolen Fayth once you are done.
