Getting Yuffie
You can get Yuffie in your party during any disc. If you're in disc two and are
riding around in the Buggy, that will work, too. The two places that she appears
most often are the forests beyond the Gold Saucer (in the Gongaga Area), and most
forests in the Junon Area. After a few battles, you'll fight Yuffie (seems to be
a 1 in 15 chance, if you ask me).
When the battle ends, you'll be in a plain with Yuffie lying nearby. There's also
a save point here. However, if you touch the Save Point, then go to your menu
screen to save, Yuffie escapes and steals 200 gil! Don't worry, you can meet her
again. You'll have to talk to her several times to get her to join. As she and you
converse, she'll ask you several questions, and you can reply in two ways. To get
her to join, respond like this:
Reply: Not interested
(talk to her again)
Reply: ......petrified
Reply: Wait a second!
Reply: ......That's right.
Reply: ......Let's hurry on.
Or in other words, choose the bottom reply, then the top one, then the bottom o
ne, and so on. After that, you can name her, and she'll hook up with Cloud and
the rest of the gang. Note that if you choose the top answer for the last question
she asks, you can name her, but she'll steal 700 gil from you and run away. You'll
have to repeat the whole process if you want to get her in your party.
Getting Vincent
When you enter the Shinra Mansion, there is a room on the left that has a piece
of paper lying on the floor. Pick it up and you'll see four clues written on it:
1. Look for the lid of the box with the most oxygen.
2. Behind the ivory's short of tea and ray.
3. The creak in the floor near the chair on the second floor. Then to the left
five steps, up nine steps, left two steps, and up six steps.
4. (nothing)
For clue 1: On the second floor, turn left, and go to the middle room. In this
room check the oxygen tank. It will say, "Right 36".
For clue 2: On the first floor, in the top left room, check behind the piano. It
will say, "Left 10".
For clue 3: On the second floor, turn right, and in the hallway, keep walking
and pressing O. When you get to the right spot (somewhere in the middle of the
hallway) it will say "Right 59".
For clue 4: This clue is written in invisible ink on the piece of paper. To
expose the message, select the blank space below clue number 3 (press the
down arrow until you select it). It will say "Right 97".
This will be the combo for the safe that is located on the second floor in the left-hand room at the top of the room.
What most people forget when trying to open the safe is that it's just like a
real combination lock... so you have to go in more than one direction when
inputting the numbers. Furthermore, unless you're fast enough, you'll run out of
time if you try any other combination. The code is:
Right to 36, Left to 10, Right to 59, Right to 97
This means that you hold right and scroll through the numbers, then hold left until you reach 10, then hold right for the last two numbers. Don't forget to press circle to verify each entry. When the safe opens, a Summon Materia (Odin) pops out, and you are assaulted by a big goon (how'd he fit into that little safe?)
Not only do you get an item from the boss once you beat it (it's the manual for Red XIII's Level 4 Limit Break, the Cosmo Memory), but there's also a gold key in the safe that you can grab (Key to the Basement). Don't forget to take the Red Materia!
The second "optional" (or hidden) character in the game, Vincent can also join your party during any disc. You'll need the gold key from the safe in Nibelheim's Shinra Mansion (see below if you don't know how to open it). Go down to the pink cavern leading to Sephiroth's library (it's in the Shinra Mansion, the entrance is in the stone wall in the eastern wing).
Remember the door to the crypt you couldn't get through? You can now enter it.
Stand at the foot of the purple coffin and hit circle. The lid will fly off and
Vincent will talk to you. To get him to join you, respond to his questions like so:
Reply: Talk about Sephiroth.
(When the coffin closes, press circle again.)
Reply: Who are you?
Then, try to leave the cavern and he'll join you. Vincent can join you from the first time you reach Nibelheim onwards.