From the phone app, you can go to options>voice mail and add the password there. It will then get auto entered when your phones dials in to voice mail.
If I'm in the phone app and hit the bb key, then select options, the top item is General Options, then under that is Voice Mail. Does your phone show something different?
Are you looking at this from your phone app? In other words, click the green phone button like you were going to make a call, then hit the bb menu button and then select options. That will bring up a new screen with voice mail being the 2nd item down from the top. I'm pretty sure your not seeing it because your not starting out from the phone app.