Getting Vincent in your party is only slightly easier thatn getting Yuffie. You get Vincent in the Shin-Ra mansion in Nibelheim, anytime after the first time you visit Nibelheim IN THE PRESENT. You can't get to him during the flashback sequence. The boss you fight to get him can be tough, but there are a few tricks to beating him.
To Get Vincent:
1. Examine the safe in the room on the right of the second floor of the Shin-Ra mansion. It's near the room where Cloud woke up in the flashback.
2. Enter the combination lock. The combination for the lock is
Just like a real lock, if you overshoot it won't work. You have 20 seconds to enter the code. It's just about enough time, but if you fail don't worry, you can try as many times as you need to. It takes some practice to get the hang of the lock.
3. When you succed in opening the safe, a boss will pop out. Lost Number is his name and he can be TOUGH. I recommend using Aeris to do this because her Seal Evil limit break will stop him, and her does enough damage to pump her limit gauge up real fast. Attack him with summons, poison, magic and limit breaks. For beating him, you will get Cosmo Memory (Red XIII's Level 4 Limit Break.)
4. After you beat Lost Number, grab the key and the Odin Materia. Head to the basement wehre you found Sephiroth in the flashback. Beware of the YinYang boss down here. If you're still hurting from Lost Number, he will wipe you out.
5. You will be able to get into the locked room in the basement, on the top of the screen where the lab door is. When you go in, stand by the coffin and talk. Vincent will pop out. Talk to him twice, and you will learn some things. When he says "Let me sleep" go and do what you need to do (go into the lab and let Sephiroth throw stuff at you.)
6. When you leave the basement, Vincent will join you.