Vodburner is a free* Windows-based program that allows you to record Skype video calls. The program features a built-in video editor that allows you to choose which video is displayed (“your side,” “their side,” or both sides) during playback and optionally add text, images and sound files to the video as well.
*The free version lasts for 14 days. During that time you can record calls between you and any other Skype user, regardless of whether or not they have Vodburner installed. After that two week period, both parties will need to have Vodburner installed on their machine in order to record Skype calls, or you can purchase a license for Vodburner ($99.95) which allows you once again record Skype video calls with anyone (without needing them to download and install Vodburner too). The paid version also allows you to export the video files as MP4 files; the free version lets you export your video as a WMV file or upload it directly to YouTube.