Just installed Call Recorder, a new Skype add-on (Mac OS X only) that lets me record both sides of a voice call as a QuickTime file. The application comes with a utility that converts the file to an MP3. With QuickTime Pro, each side of the call can be separated into a channel, which is handy to boost one side or the other when someone talks softly.
Give the high quality of Skype, this is an excellent interview tool.
Caution: It’s illegal in some places to record other people on the phone without permission. I don’t know if this law applies to Skype, but it’s not honorable to record someone else without permission no matter what the medium.