The Cavern of the Stolen Fayth is an optional area you can visit either while on your way to Zanarkand, or when you get free reign of the airship. It is located after the northeastern exit of the Calm Lands, cross the bridge and then turn right and head down into the valley. There you'll find a Save Sphere, so save if you like. Now, we enter the Cavern of the Stolen Fayth.
The Cavern of the Stolen Fayth
When you first enter, there aren't any other paths, so just continue forward until you reach a fork in the road. Choose the fork to the right, when you'll see a dead end and a chest that has the item Megalixir in it. Continue forwards until you reach a room where you get a short cut scene, and then just continue onward until you get to the crossroads. Choose the right path, to reach a room with a chest containing a Lvl. 2 Key Sphere, return to the junction, and head left.
You will soon reach another crossroads, continue forwards if you want to reach a chest containing a hard-to-get Fortune Sphere. Return to the fork you just left again, and again head left.
For one last time, you reach a crossroads. Head left for the Al Bhed Primer XXV, then head right to reach the Save Sphere (Highly recommended that you save here. Boss fight soon.), and head north for Mega-Potion x2. Continue east to reach a boss battle against Yojimbo.
Yojimbo has 35,000 HP and is pretty nimble (he can evade attacks quite well). Yojimbo's dog will attack you (Daigoro) for a nominal amount of damage, and Yojimbo himself will attack you for a bit more (Kozuka does about 500 damage to everyone and inflicts Poison). The trick here is to take him down before his Overdrive bar reaches its limit, as his Overdrive is devastating - Wakizashi does a lot of damage indeed. Defeat him using overdrives and regular attacks, or if you feel like it, treat this as an Aeon battle and bring out Yuna - Shiva or Bahamut are both good enough to tear down Yojimbo.
Further Exploration & Bargaining with Yojimbo
Stand upon the glowing pedestal and face the right. Press to teleport to a room that has two chests - one with an MP Sphere and the other with X-Potion x2 and the room on the left of the teleportation device has a chest with Rikku's weapon Flexible Arm.
Take the teleport forwards to reach the Chamber of the Fayth. One wonders what Yojimbo does with the money he extorts out of summoners, as that's how he operates - he demands money. The more money you give him, the more likely he is going to use a good move. He thus has no usable Overdrive, unless you get him to really like you (ie, by giving him money to make a move), both of which increase his chances of using his better attacks, namely Wakizashi and the infamous Zanmato which instantly kills every enemy 100% of the time and even works on the likes of the Dark Aeons, Penance, and the Monster Arena creations.
In order to gain Yojimbo into your small army of Aeons, you will have to pay a lump sum to get him to join you. To minimize this cost, follow these instructions:
When asked what you want, answer 'to defeat the greatest of enemies'. Yojimbo will then offer a sum (250,000 gil). If you pay that amount, he'll join you. Better still, though, is to offer half that number plus one gil. Next, offer half the sum he then offers you plus one. This is as low as he will go - try to haggle any farther, he'll kick you out of the place.