Skype Call Recorder is a free open source solution for recording Skype conversations on Linux.
There is also an experimental version for Windows, but I’ve not tried that, so this review is only about the Linux version.
Skype Call Recorder is available ready compiled for several Linux distributions from their web site: http://atdot.ch/scr/
On Ubuntu, installation is just a matter of downloading the package ( the .deb file) and authorising the software centre to install it.
Assuming that you already have a correctly functioning installation of Skype, configuring the recorder is extremely easy - just run the program and follow the brief on screen instructions. Setting it up takes about 30 seconds.
By default, Skype Call Recorder will record the local microphone on the the left channel and the remote voice on the right channel, which is ideal for later editing in Audacity. If preferred, it may be configured to mix both channels together.
This software is currently at version 0.8, but from my brief tests it gets a full 5 start rating.
SPAM WARNING: Recommendations from personal experience of genuinely free Skype recording software is welcome, but Skype recording programs are one of the most common spam subjects. Please do not reply to this post with adverts or links to non-free, (including advert supported, demo, trialware and pirate version of commercial programs) as there is a very high chance that one of the forum moderators will ban you from this forum.
For commercial software, Pamela is known to work and there is a free version (recording duration limited to 15 minutes).