Yep, that's what happened when I upgraded. Activated in the store, restored from a backup when I got home, and didn't skip a beat. All voicemail was there, as well as everything else. The only tough part was sitting waiting for all 16GB of music and video to transfer.
And actually, the iPhone does keep local copies. If you jailbreak and ssh into the iphone, you can find them in /private/var/mobile/Library/Voicemail/