On Windows my sound drivers include something called stereo mix. You can record this through audacity to get their side of the conversation. To record yourself as well you need to set your mic to playback through your speakers, but then you hear yourself speaking.
There may be a better way, but that's what I've always done if I needed to record on Skype.
It probably depends on your sound card, and whether it can record from more than one source at a time. Many older sound cards only had a single stereo input, but it's not uncommon for newish motherboard-integrated HD Audio chipsets to support recording from multiple sources.
If you (still) use an emu10kn-based card (such as the SB Live), the kX project drivers allow custom routing, mixing, and alteration of inputs and outputs via the card's built-in DSP chip.
There may be a better way, but that's what I've always done if I needed to record on Skype.