Call your voicemail and listen to the prompts. If you don't hear one for changing the message, try one for "more options". If you don't hear that either, try calling 611 (on your cellphone) and ask them to help you.
The carrier runs its own voicemail server, so each one is different.