When you're out of Midgar, and wondering around the forests near to Fort Condor, you may just encounter a mystery ninja.
Now finding her isn't so hard. But trying to convince her to be in your team without the proper instrutions is slightly more trickier.
When you have beaten her in battle, you'll appear in a clearing with her on the floor, and a save point.
DO NOT, I repeat, DO NOT turn your back on her. A thief cannot be trusted. Therefore do not check the save point. Go straight to her to see if she is okay. She'll show her gratitude by saying:
"You spikey-headed jerk! Let's go one more time!"
I suggest you reply with:
"Not interested."
Now she's feeling cocky, so she taunts you. Talk to her again.
Yuffie: "You're pretty scared of me, huh?"
Answer: "......petrified."
She'll start to leave.
Yuffie: I'm really gonna leave! REALLY!"
Answer: "Wait a second!!"
She seems to be getting the picture.
Yuffie: "You want me to go with you?"
Answer: "......That's right."
Yuffie: "All right! I'll go with you!"
Answer: "......Let's hurry on."
And there ya go. Yuffie Kisaragi is under your command. Kind of.
How to get Vincent:
Vincent Valentine is locked up in the Shinra Masion in Nibelheim. When you get there, (In person not the memory) there are some notes lying about the floor with clues on how to get Vincent.
But who needs little notes when you have a walkthrough like this?
You need to open the safe first. This is found upstairs to the left in one of the rooms. The combination is:
Right 36
Left 10
Right 59
Right 97
You have 20 seconds to enter it correctly, and don't go past any number while entering the combination or it won't work.
You will be attacked by a boss, Lost Number.
Red side is magic, and purple side is phsyical. Before the fight, put Aeris in your group with her Limit break on 1. She can cast Seal Evil which should paralyze the monster for most of the battle.
When it's dead, you get the basement key, summon Odin, and Cosmo Memory, Red XIII's final limit break.
Return to the basement area using the same path you used in Cloud's flashback at Kalm Inn. Use the basement key on the door you couldn't enter. There's Vinnie.
Talk to him about Sephiroth; he'll go back inside his coffin, but don't give up. Talk to him again and you'll get his name. He'll ask you about a lady named Lucrecia, who he claims gave birth to Sephiroth. After getting this bit of info Vincent won't open his coffin again.
Leave and continue into the libary and talk with Sephiroth. Then leave. When you start to leave, Vincent appears and joins you.