How do I change my voicemail recording on my Nokia mobile?

Well first thing you need to do is call your voicemail number.
This can be found in either the manual, or maybe on the nokia website (it's usually saved as speed dial #1 on your phone.)

If your having trouble finding the number, you can always try calling your own number from your own phone.
This should put you straight onto voicemail settings, and from there you just follow the directions.