Vincent is pretty easy to get, which is pretty nice considering how damn cool he is.
First, go to Shinra's Mansion in Nibelheim.
Then, unlock the safe on the top floor and fight the boss. Kick his ass and you will get the basement key.
Go to the basement and unlock the door in the hallway. See Vincent sleeping in his casket and wake his ass up.
Ask him about Sephiroth, and he will speak all crypticaly and go back to sleep. Bother him again and get his name (name him something like Earl), and after telling you about how his soul is dark and without hope, he will bore himself back to sleep.
Head out of the Mansion. He'll stop you and join the team (but not before reading you some poetry by Robert Smith) .
Now you have a cool Gothic member on your team. Remember the Alamo~!