All iPhones that are used on an authorized network should have visual voicemail. I assume that you are in the United States and using AT&T?
I have a 1st gen iPhone & my friends bought the new 3G, but due to the hose-up with the servers on Friday he waited until after 5pm (17h) to activate his phone. He had his account converted from a regular LG phone over to the iPhone. The voicemail for the new iPhone account was setup, but not activated.
I assume that you haven't setup your voicemail? Using your iPhone, call your own telephone number. You should get a voice prompt, telling you that your voicemail isn't setup yet. You will need to make up a passcode for your voicemail. It will give you a brief overview of the V/M system. You can make a personal greeting, if you want.
After the setup is completed, disconnect your call. Now, go to the HOME screen and select the SETTINGS icon (gears). Scroll down to the green Phone icon, and select it. Scroll down to and find the button that says, "Change Voicemail Password". Input your passcode.
Your visual voicemail should work now by using the voicemail button. You will not have to enter the passcode from the iPhone to work the voicemail. If you are away from your iPhone; you can call your iPhone number, after it goes to voicemail, then you can press the asterisk "*" key, input your passcode to access your voicemail.
The V/M access telephone number is in Minnesota and isn't something that you would call from a landline to setup your account, or call to check your messages; because it is more than likely a long distance call for land-line users.
The voicemails are basically audio files, (either AAC or MP3), that are downloaded to the phone with some type of meta-tag. There is some type of inter-action with the voicemail platform and these audio files on the phone. If you are on a plane or in a subway tunnel, you cannot listen to your messages. However; if a voicemail is put into the deleted bucket, you can.
I hope this helps out. If not, you will need to contact your provider for assistance.
