Popular answer Go to this answer
I have verified dlupresto's solution. Here are the steps I followed:
1) Install GV, and follow setup until it hangs at "reading settings."
2) Reboot phone (canceling the process didn't stop the "reading settings" hang for me).
3) Log in to GV on the web, go to Settings, and choose to activate your phone. DIAL THE NUMBER THE WEBSITE GIVES YOU, it will not work if you use *71yourmobilenumber, like the GV mobile app has you dial (callers will get a busy signal).
4) After following these instructions, it did not matter if my voicemail service was configured as Google Voice or My Carrier. Both ways, it goes to GV.
5) Make sure you have your settings in GV on the web set to NOT text you or email you when you get a new message. Until I disabled these, I was getting 3 notifications on my phone whenever a voicemail was left. I'd simultaneously get an email, a text, and the GV notification.
I hope this helps!