Yojimbo - Caverns of the Stolen Fayth
Yojimbo can be found in the Caverns of the Stolen Fayth which is just off of the Calm Lands. You pass by it through the regular story of the game on your way to Mt. Gagazet; the entrance to the cave can be seen in my screenshot that's below.
If you're coming back to this cave after you've gotten the Airship it'll be a total breeze to clear it and acquire Yojimbo. The difficulty of the cave is about on par with the monsters you fight in Mt. Gagazet and you can easily complete it on your fast pass through of the Calm Lands.
I strongly recommend you use Capture weapons when fighting in the Caverns of Stolen Fayth which you purchase from the Calm Lands Monster Arena. Use that link to learn more about the Monster Arena and all of the rewards it can give you for participating. It's by far the best way to min/max your characters there is. If you know what you're doing you can get 99 Sphere Grid levels in 15 minutes.
Inside the Caverns of the Stolen Fayth you'll encounter some new enemies you may not have seen elsewhere yet, such as the Tonberry. You'll also encounter Magic Urns inside of here which you can't kill but rather you have to select random eyes on them to try and guess 'Bingos'. Guessing one correctly will net you an item reward.
Aside from those two enemies not much else makes this cave unique; It's fairly linear and easy to navigate. In the back of the cave you'll find a teleport pad, left and right take you to treasures and forward will take you to Yojimbo's Room.
Inside Yojimbo's room you'll view a short cutscene and then you'll be asked to pay for Yojimbo's services with 3 possible options to choose from. The option you choose will determine the initial cost of Yojimbo; the third option "To defeat the most powerful enemies" is the cheapest one.
Yojimbo will ask 250,000gil of you and you can haggle with him up to 3 times offering him half of his offer +1. So at 250,000gil offer him 125,001. He'll lower his asking price for you a total of three times. Much like your initial experience with Yojimbo, each time you want to use this Aeon you'll have to pay him a lump sum of Gil.
You will need to acquire Yojimbo as well as Anima and the Magus Sister in order to get Yuna's Celestial Weapon, Nirvana.