Skype Call Recorder is an open source tool that allows you to
record your Skype calls on Linux. Current features include:
1.  record calls to MP3, Ogg Vorbis, or WAV files
2. Automatic and manual recording
3. Configure automatic recording on per-caller basis
4. Split stereo recording

This requires lame and id3lib.