You cannot get Yojimbo until you progress through the Calm Lands and you MUST have about 200,000 gil! Once you've exited the Calm Lands through the north exit, you'll come across a bridge with a save point near it. Save and do the story event on the bridge, then instead of crossing the bridge go to the right of it and walk around underneath it.
This will bring you to a new area with an entrance to a cave. Progress through the cave (watch out for Tonberries!) and once you reach the end you'll get a cutscene and a pretty easy boss fight against
.
After the boss fight, make sure you use the teleport pad to get the items to the left and right, and then use the pad to go north. Yojimbo will be here, and he'll want to negotiate. For his first question, pick the third option, and his starting offer will then be 250,000 gil. Bid 125,001 and he'll lower the offer. Bid 125,002 and he'll lower the offer again. Bid 200,000 and boom, you've got yourself Yojimbo.