Yuffie
Once and a while, er, alot of times, you'll notice that there's these woods/forest things. Keep running around in them. Once and a while, a person labeled as "Mysterious Ninja" will show up. After beating her, she'll be lying on the ground near a save point. DON'T USE THE SAVE POINT. Go up to the girl and talk to her. She'll ask you a bunch of questions. Answer them as followed and you'll be able to have your gil back and you'll get to control this ninja for the rest of the game. Answer her questions Bottem Choice, Top Choice, Bottem Choice, Top Choice, Bottem Choice. That should do it!

Vincent
In the shinra mansion in nibelhelm, there's safe. it has a key to the basement room. In order to get Vincent, Odin and Cosmo Memory, you must open the safe. The combo is Right 36, Left 10, Right 59 and Right 97. Don't go past any number while opening or your screwed. And make sure everyone in your party has been fully healed, cause once you open the safe, a boss called "Lost Number" will pop out. After, go down to the basement and there's a little door that leads into another room. (it's located like right before the study door). Go in it and go up to the middle coffin. Vincent will pop out. Get him to tell you about Sephiroth and Lucreia (if barret's in your team, at one point he'll say "so you decided to sleep in a box?). After, talk to him again and get him to tell you his name. When you go upstairs, vincent will stop you and join your team, since he was a Turk, he might be some help ^^ (not really, but his limits rule).