First, a quick note: to do this, you'll need a Google Voice account. After many, many months in private beta, Voice is finally starting to loosen up a bit, but it's still not a free-for-all; if you don't have an account, go to voice.google.com right this second and request an invite so that you can get in on this as soon as possible.
To begin, log into your Google Voice account by navigating to voice.google.com. Click on Settings at the top right of the page. If you haven't yet tied your cellphone to your Voice account, you'll want to do that now by clicking on the Phones tab and following the instructions on the screen.
After you've done that, click on the General tab in Settings. This is a good opportunity for you to set up your recorded name and voicemail greeting (they're the third and fourth settings in the list). Google does this by actually calling you and asking you to record them over your phone, just as you would with any other voicemail system -- you don't need a studio-quality mic attached to your PC or anything fancy like that.
The idea behind Google Voice -- better expressed by its former name "Grand Central" -- is that you're given a new phone number that acts as a central clearinghouse for all calls coming into you. In other words, you give out your Google Voice number instead of your landline or your cellphone number, and Google routes the call to you. That's great, but the problem with that plan (assuming you're okay with Google owning your main phone number) is that they're currently not allowing you to port numbers in to the system, which for many folks is a deal-breaker.
That's okay, though, because we're going to effectively use Google Voice backwards. Crazy, right?
"But if I'm not giving out my Google phone number," you're thinking, "why do I need to make sure it doesn't forward to my cellphone when someone calls it?" Good question! The answer is that you'll be calling your Google number yourself. By default, your phone is configured to call a number assigned to you by your carrier if you don't answer, your line's busy, or your out of coverage; this is the number that takes callers' voicemails and plays them back to you when you press and hold the 1 key on your phone.
What you may not have known is that you can change this number to whatever you want! We don't want to use our carrier's lame voicemail system anymore, so we're going to have 'em forward unanswered calls to our Google Voice number instead -- which will go straight to our Google Voice voicemail. Pretty neat, huh?
Now that we have Google Voice itself configured the way we want, we have to set up the proper call forwarding on our phones. Some Android devices have a menu in Settings where you can do this totally painlessly.
If you were unable to find any of these menu items, you'll need to proceed to Plan B -- programming those three call forwarding settings by dialing GSM codes, which AT&T has a good guide on here. These codes are standard across carriers; obviously, your mileage may vary, but they should work.
Good news -- you're almost done! The last piece of the puzzle is to install an app on your phone that'll allow you to access your Google Voice account. Google doesn't have one yet -- which we find a little bizarre -- but in the meantime, there's an excellent third-party substitute in the Android Market called GV. Grab it and install it.
The first time you run GV, you'll be asked to save your Google Voice login and voicemail PIN (make sure you've set this up on the Google Voice site first) so the app can do its thing. You'll also be to configure some settings. For this setup, we recommend that you uncheck "Route all calls through GV," and set "Check for new" to 15 minutes. You can have it check for voicemail more frequently than that if you like, but it'll hasten battery drain a bit.
Pretty cool, huh? The developer of GV warns that Google hasn't released an actual API for developers wanting to code against Google Voice services, so the app cheats a bit by relying on certain HTML elements of the service's mobile site. If you like what you see (and we know we certainly do), be sure to let Google know that you want them to expose an API -- and while they're at it, release an official app!