Might be good to find out whether or not it's legal in your area first. You probably have to tell them you're recording.

Beyond that, I guess if you have a phone with a headphone jack (most cordless phones these days seem to), you could get the appropriate cables/adapters and route them into your computer, recording the audio with some recording software. I did this once to record a particularly humorous message a friend left on my voicemail.

Actually, now that I think about it, I think this will only get you their end of the conversation. That probably wouldn't help you much...