Yuffie-- While roaming around in a forest, you may run into a strange little girl named Yuffie Kisaragi.  Yuffie is a female ninja and a materia hunter.  Finding her isn't always easy.  You have to walk or drive around into any forest area until you encounter her.  Yuffie appears just like any other enemy creature, but she has the temporary name "Mystery Ninja."  She's a tough fighter, but you should be able to defeat her without much trouble.  After defeating her, you'll go to a small map that has a Save Point.  Yuffie is lying down here, but she's fine.  Examine her and you'll start a long dialogue.  First, don't use the Save Point.  Now, examine Yuffie and she may challenge you to a fight.
Yuffie: You spikey-headed jerk!  One more time, let's go one more time!  Answer: Not interested.  Yuffie: You're pretty scared of me, huh!?  Answer: ...petrified
Yuffie: I'm really gonna leave!  REALLY!  Answer: Wait a second!  Yuffie: You want me to go with you?  Answer: ....That's right.  Yuffie: Alright!  I'll go with you!  Answer: ....Let's hurry on.    You've done it!  You have Yuffie.  She sucks, but she's part of the story, and has the "Throw" Materia.

Vincent-- Vincent is locked away in the Shin-Ra Mansion's basement.  The door to his room is locked, but the key is easily obtained . . . sort of.  Unlock the safe on the top floor of the Shin-Ra Mansion (combination Right 36, Left 10, Right 59, Right 97) and fight the Boss, Lost Number.  After winning the battle, you'll find the Basement Key in the safe (as well as the "Odin" Materia on the floor).  Go downstairs, unlock the door, and talk to Vincent, who's resting in the center coffin.  Tell him about Sephiroth and he'll return to sleep.  Wake him again and get him to tell you his name.  He'll go back to sleep again, but on your way out of the Shin-Ra mansion, he'll stop you and join the team.  You've done it!  You have Vincent.  This dude is one helluva kickass character with a strange origin.  He will prove most helpful to you in future battles.