I just set up Visual Voicemail with GoogleVoice and it works great.
Here is the order of operations for Voice Mail (I don't do SMS):
1. Sign up for Google Voice
2. Choose the setup option online for voicemail (it was in the initial startup screen, but since you already have an account, it may be under settings instead now)
3. Google will call you and have you punch in a verification code.
4. Once verified, and your carrier is identified correctly, Google Voice will give you a code to dial on your phone that changes where your voicemail comes from.
5. Download and install the GoogleVoice app from the Android Market.
6. Have it configure your voice mail settings, and tell it how you want to handle outgoing calls (international, ask, or none)
7. Go back to your GoogleVoice account online and deactivate the email and text notifications, otherwise you will get a VM indicator, a text and an email everytime someone leaves a voice mail.
Hope this is helpful. Be sure to click on "Thanks" if it was.