Is this possible? Say 2 or more people all had Skype or similar. Can it all be recorded somehow, and if so, what is the quality like?

Audacity and the lame_enc file for exporting to mp3.

The sound quality will be as good as you will hear it for yourselfs

Cool, thanks Adam!