Everyone everywhere needs google voice, but if you're a new android user (and a lot of my friends seem to be), sign up right now. You probably won't use all of the service, but the voicemail transcription alone is completely worth it.
Go to google.com/voice and pick a phone number. It doesn't matter what it is - the primary use for this is giving it to companies (or dates, I suppose) who you want to be able to ignore in the future. You'll go through the first-run flow, and have to add and confirm a phone number; add your android's number here.
Now go to Market, and install the Voice application. It'll go through a little first-run flow as well (when it asks, select "only use google voice for international calls"), and then ask you to use google voice as your voicemail. This is the thing you want!
There'll be a bunch of other neat stuff you can do - cheap international calls, avoiding text messaging charges from your carrier - but the core functionality is awesome, free voicemail.