Getting Yuffie Kisaragi
You can aquire Yuffie at any time of the game. But I suggest getting her in the start of the game. The two most places she appears are in the forests (beyond Goldsaucer) and most forests in the Junon Area.

Just simply fight Yuffie. It isn't a very difficult battle. Once Yuffie joins your party her HP and MP vary on what level your other characters are at.

When the battle ends, you'll be in a plain with Yuffie lying nearby. There's also a Save Point here. But what ever you do, do not touch that save point Yuffie will steal 200 gil from you and run off. But you can still meet her again. Just becomes frustrating. You will have to talk to her many times before she joins you. But be careful of what you say. She will 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 one, 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. I tell you it isn't a walk in a park.

Getting Vincent Valentine
The second "optional" character in the game is Vincent. Vincent is in Nibleheim in the Shinra Mansion. Shinra Mansion? Shinra Mansion is up the stairs of the town with the gates. The only way you can get that locked door down stairs is getting that special key. It is in the safe. The code is: RIGHT 36, LEFT 10, RIGHT 59, RIGHT 97 Go back down stairs, the door is on the eastern wing. 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 O 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 (but not during Cloud's flashback).