Setting up a new voicemail service will vary depending on which carrier you have an account with -- i.e. from what I recall I had to start up the Phone app and in the dialpad press and hold the 1 key. That brought up a prompt to set a passcode, record my greeting, etc. Your best source on instructions would be just go to your chosen carrier's web site and find the page where they provide their voicemail setup details.