Here is a chart on how to find the hidden characters Vincent and Yuffie.



Finding Yuffie

In order to find Yuffie, go to the forest surrounding the Ancient Temple (at least, this is where I found her. I heard that you can find Yuffie in any forested area). There you will fight a "Mystery Ninja." She shouldn't be too tough to beat, but she uses a great deal of Fire magic, so equip accordingly. After you defeat her, the party appears in a grassy area with Yuffie on the ground. You must then enter a long conversation with her, and she will join your party. Easy, right? Well, I should probably mention that if you say even 1 thing wrong, she will run away and steal your money. Dont worry, though, because you get way more money after you beat her in battle than she steals.

The trick to this is to never take your eyes off of Yuffie. In game terms, this means never access a menu. First-timers will be thrilled at finding a save point near Yuffie. DONT USE IT, or she will be gone when you exit the screen (which while in, by the way, you still cannot save) and you will lose some gil. That said, just never access a menu. dont even go into a menu to give Yuffie a name, she will just be gone when you come out. She will name herself, dont worry.
For the more impatient, however, here are her questions and your answers:

Yuffie: You spikey-headed jerk! One more time, lets go one more time!
You: Not interested

Yuffie: You're pretty scared of me, huh?
You: ....petrified.

Yuffie: I'm really gonna leave! REALLY!
You: Wait a second!

Yuffie: You want me to go with you?
You: ....That's right.

Yuffie: All right! I'll go with you!
You: Let's hurry on.

Finding Vincent

Vincent is a little more of a puzzle to obtain than Yuffie. You have to run around Shinra Mansion in Nibelheim solving some puzzles to obtain him. Here are the locations to the five hints in Shinra Mansion:

1. The Atrium upstairs. There is a treausre chest. Open it, and then search the back of the lid.

2. The Piano in the Music Room.

3. From a squeaky point next to the chair in the upstairs bedroom, go left five steps, up nine, left two and up six.

4. The last clue is on the actual paper, written in invisible ink. Just look at it, and Cloud will be able to read it.

Once agai, if you are too impatient to go through all the clues, here is the combo for the safe: Right 36, Left 10, Right 59, Right 97. Be sure not to go past any of the numbers, or the combo wont work and you have to start over again. You are also on a time limit, so work quickly and carefully. Defeat the monster that jumps out at you (sometimes easier said than done...) and get the key and Odin materia.

Now go downstairs, almost to the library you see Sephiroth. In the basement passageway, look for a door on the wall. Open it with the key, and talk to Vincent. He will join your party when you leave.