In the Shinra Mansion in Neibelheim, there's a puzzle you can solve that will get you several powerful items, as well as Vincent. As you first enter, look on in the left alcove. You should see a little notehanging on the wall that gives you some information about where to find the combination foir the safe. You can find the answers to the clues on the note with a bit of detective work (there's one on top of the chest in the upper left room, there's one behind the piano, there's one by a chair, and the last one's right there on the note, in the fourth invisible slot), but if you're not interested in running around doing things the hard way, here's the solution:
right 36
left 10
right 59
right 97
Remember, this safe works like a real combination lock, so you can't overshoot any numbers, and you have to do it all in 20 seconds. You'll probably get it after a couple tries or so. But be ready to fight, though, because out of the safe pops a fairly tough boss, the Lost Number! Big Guard will help a lot here, so cast it right away. That should protect you from the damaging attacks Lost Number uses on you, letting you dish out some damage of your own. Summon spells, high level magic, and maybe a Deathblow or two will finish him off fairly quickly. Just make sure you use Big Guard at the start of the battle. When you're finished, you'll get Odin Summon, Red XIII's level 4 limit break, and the key to the basement.
Now, you can go down to the basement and try out that new key you got. Go down to the cave area just before the library. Examine the door at the north wall. using the key, you can open it now. Go examine the center-most coffin, and Vincent will pop out and speak with you for a while. When you're speaking to him, don't keep any secrets from him. When he says "Let me sleep..." then go and do your business in the library. As you leave for the stairs again, Vincent will wake up and tell you that he wants to join you. He'll then be permanently in your party. he can be added any time using the PHS.