Yep, you need to login to your GV account from a PC or Mac first to set everything up. It will then send you a confirmation code, then you enter it into GV, then your device will setup voicemail on it's own. At least mine did. So now whenever someone calls my Verizon number, and I let it roll to VM, it goes to GV, plays a custom greeting (based on who's calling), then they can leave a message.
If they do, then I can open up GV on the Thunderbolt and play the message; If they don't leave a message, then it just shows a notification of a missed call. They also have a transcribe feature, but it's kinda buggy, doesn't work to well.