From StrategyWiki, the free strategy guide and walkthrough wiki

This section covers how to get the two optional characters to join. Getting both of them is highly recommended: Yuffie's sidequest gives you some interesting materia, and Vincent is a devastating fighter with all-around long-range weapons and amazing limit breaks, and getting him also gives you some interesting items and materia.

[edit] Yuffie

You will run into Yuffie randomly in the woods. The earliest opportunity to get Yuffie is before going to the Junon for the first time. The woods are to the east and to the south of the town. You can also run into Yuffie on the central continent, south of Corel Desert / Gongaga area, southeast of Cosmo Canyon.

Yuffie will first appear as a "Mystery Ninja." Her stats are different depending on the party level, but should never be too hard to defeat.

After the fight, you find yourself on an empty clearing, talking to Yuffie, who wants to fight again. Do not open the menu or Yuffie will steal your Gil - subsequently, do not use the save point as this is just a ruse to get you to open the menu. Keep talking to her and she will join you. You need to pick the correct dialogue choices basically on instinct and trial and error, and if you fail, don't worry, just find the Mystery Ninja again in the woods and you'll get to try again.

If you don't want to guess, the correct dialogue choices are:

Choice 2  · Choice 1  · Choice 2  · Choice 1  · Choice 2

The actual lines are different depending on who leads the party:

As a side note, in case you haven't noticed this, Yuffie calls Cloud a "spikey-headed jerk", Tifa "boobs" and Cid a "bow-legged old man".

[edit] Vincent

You can find Vincent any time you are in Nibelheim (in present time, that is - not during the Cloud's flashback early in the game, of course). On the lobby desk of the Shinra Manor there's a book that has hints on finding out the correct combination to the safe upstairs.

• First hint: Lid of the box with most oxygen. There's a box in the greenhouse, open it, and then use it again to examine the lid.
• Second hint: Behind the Ivory's short of tea and ray. This is probably the most frustrating riddle to figure out (especially since piano keys are no longer made of ivory and we rather prefer to call the notes 'ti' and 're' anyway). Examine the surroundings of the piano.
• Third hint: Find the creaking floor on the second floor, on the right side, near the chair, then go left five steps, up nine steps, left two steps, and up six steps. Note that this refers to actual walk animations rather than key presses, so quit running for a while and count the paces. You will end up in the short hallway on the second floor. Examine the surroundings there to find the hint.
• Fourth hint: It is given right in the book, but the entry itself is invisible; simply move the pointer to the 4th slot to learn the last move directly.

If you don't want to chase the hints, here's the code right away:

Right 36  · Left 10  · Right 59  · Right 97

When opening the safe, stop on those numbers exactly and hit the button. If you slip, you need to start over. The safe door should open with a little bit of practice. But the following fight needs no practice, just a coherent strategy.

The boss will leave behind a lot of interesting things: Cosmo Memory (the manual for Red XIII's Level 4 limit break), The Odin summon materia, and - lastly - the key to the basement!

Now head to the cellars where you visited during Cloud's flashback. With the key, you'll be able to open the door north in the room that led to the library door. Open the coffin in the middle and Vincent awakens. Talk to him about Sephiroth. He will doze off again, so open the coffin again. Ask "Who are you?" Then there's nothing more to do, so head back out towards the stairs up. Vincent will stop you, and will then follow you.