Voicemail isn't usually stored on a phone itself. It's normally stored on your phone provider's system. So listening to a voicemail is no different to listening to any other call. If your phone has the ability to record calls (which some might have but many won't) you can simply record the 'call' as you listen to the message.
Make and model of phone, please?
Otherwise you'll need to play the message on your phone and hold it close to some sort of recording device (such as the microphone on a laptop) or possibly connect a lead from the headphone socket on your phone to the 'line in' (or 'mic') socket on your laptop, PC or other device with a recording capability.
It's hard to answer this one without knowing what type of recording devices you've got available!