Telemark - A type of turn named after the place were it was invented (Telemark, Norway). In this turn, the inside knee drops low and the inside ski drops back creating a high degree of fore-aft stability (and the heel of that foot comes up). Telemark gear is designed to accommodate this technique with a toe piece that holds the toe securely and a strong cable that wraps around the heel pulling it into the toe-piece (giving it more stability). Unlike cross country, telemark gear is designed for skiing down steeper and more aggressive slopes. Metal edge skis with smooth surfaces (just like alpine skis) are used. Also capable of climbing uphill or across flat terrain with skins attached to the bases (synthetic fur that is smooth one way, rough he other allowing forward slide but traction when pushing back. these are put on and taken off as needed).
Cross County - Free heel like telemark gear, but much lighter (faster, requires less energy). This gear is not as as strong as telemark gear and does not accommodate aggressive downhill skiing. Bindings lock in toe, but do not have a cable (much less stability) and skis usually do not have a metal edge (not good edge control). Often these skis have "fish scales" or special wax that allows forward slide but traction when pushing back. Cross country skiing is about touring rolling hills and flatter terrain.
Randonee - Also called "Alpine Touring" or "AT". The heel can be free to climb or cross flat terrain, but locked to descend using the typical alpine skiing parallel turn. Skins used just as with telemark for backcountry access. these are lighter than alpine gear, but typically heavier than telemark gear (thought he gap is closing). Suitable for aggressive, steep terrain (like tele, but unlike cross country).
Hope that helps!