In my prior experience with Android phones, when you setup Google Voice, it offers to change your default voicemail provider. It would send you to the Settings -> Call Settings page. Normally, you'd have a "Voicemail Service" option to select a different voicemail service than Sprint's default. Here I'd select Google Voice.
Unfortunately, the option is blocked or missing on my LG Optimus S. I'd like to see this fixed in a maintenance update.