Yojimbo is the first of three optional Aeons that you can obtain. He is the easiest of the three to obtain and can be picked up during the regular story mode when you pass by the Cavern of the Stolen Fayth. That said, it is much easier to return to the Cavern later on in the game.
Check out the Cavern of the Stolen Fayth side quest section for more information. You can also refer to the Calm Lands walkthrough page for additional details about when you can obtain this Aeon:
25) Calm Lands
Arriving at the Calm Lands, exploring Remiem Temple for the first time, visiting the Monster Arena and completing the Chocobo Trainer side quests.
Cavern of the Stolen Fayth
This side quest can be completed as soon as you reach the Calm Lands and is where you obtain the optional Aeon Yojimbo.
Yojimbo is not like any of the other Aeons in the game. You have to pay Yojimbo each time you want him to attack and his attack will differ depending on how much or how little you pay him as well as if your alignment with Yojimbo is high (not letting him die, never paying him 0 gil, not immediately dismissing him after summoning him). Your alignment with him will rise the more you use him. He has the following attacks:
Daigoro: Yojimbo’s weakest attack - his dog will conduct the attack for him. This is Yojimbo’s indication that the amount of gil you provided to him was not enough.
Kozuka: Yojimbo throws throwing stars at a single target.
Wakizashi: Yojimbo does a large slash through the air and ground that can either hit one target or multiple targets with his wakizashi sword.
Zanmato: Slices enemies in half ending the battle instantly (similar to Odin / Gilgamesh from Final Fantasy VIII)
Yojimbo will be able to exceed 9,999 damage after Auron has obtained his Celestial Weapon, 
Masamune.
