Getting Vincent In Your Party

Finding Vincent is easier than finding Yuffie. Here's how to do it:
Step 1: First open the safe in Shinra Mansion (see below for code) and defeat Lost Number.

RIGHT TO 36
LEFT TO 10
RIGHT TO 59
RIGHT TO 97

Step 2: After defeating Lost Number (easy kill), check the safe to get the key item "Basement Key". (And don't miss the easily accessed Odin Materia nearby either.)

Step 3: open the secret door Cloud used in the flashback and enter the basement cave, once inside, open the Wooden door using the key.

Step 4: "Talk" to the coffin in the middle of the room; Vincent will awake and ask to talk for a while:

Vincent: What do you want? (This isn't exactly what he says.)
Response: Talk about Sephiroth.

They'll talk for a while, then Vincent will go back to sleep.

Step 5: Press O again and Vincent will reappear.

Vincent: What is it this time?
Response: Who are you?

Vincent will explain a bit about himself, then you'll get to name him. He will go back to sleep. Just continue on to the meeting with Sephiroth at the end of the basement. When you start to leave, Vincent will appear and offer to join the party.