One of the most requested features of Skype is the possibility to record calls. As of yet, it still has to be implemented into Skype itself. But that is no longer that big of an issue, because there are now third-party plug-ins to do this. For Windows there's the free Skype Recorder. Apparently this program can also record other VoIP phone converstations (such as Google Talk). Personally I haven't tested this software, but it should work.
For the Mac there is Ecamm's Call Recorder, which costs $13.46. I tested this myself and it works really nicely. It integrates into Skype itself (also adds a tab to its settings window). It records the conversations into a Quicktime movie, which sounds weird, because it's only audio. The reason they do this is to be able to record two tracks separately. On one track it will be you talking and on the other the person(s) you're talking to. This way you can edit each track separately. Little utilities are included to easily mix-down this movie into AAC or MP3.