In practice, space is near enough at the temperature of the [[http://en.wikipedia.org/wiki/Cosmic_microwave_background_radiation cosmic microwave background radiation]], energy which permeates the known universe at a temperature of about 3 kelvin, provided that you're made out of normal matter and you aren't near anything hot, like a galaxy. While the first is true for most protagonists, very few stories are set in the intergalactic void, even though it accounts for most of the volume of the universe.
The fallacy arises when people conclude you'll freeze down to 3 kelvin if you go out there. This is true in the long run; a person (or any other object) left in space for a prolonged period of time would cool down to the temperature of the surrounding space.
There are however two caveats to keep in mind. First, this temperature will only be as low as 3 kelvin if there aren't any other radiation sources (like, say, stars) anywhere nearby: anyone exposed to starlight in space is actually in danger of roasting to death, not freezing. (For proof, go outside on a hot day, and keep in mind that you have a lot of atmosphere protecting you while you do so. In orbit, it'd be worse.) Second, the "prolonged period of time" required for the human body to freeze in a totally dark vacuum is measured in hours, not the seconds (and definitely not the instant flash-freezing) usually shown in movies.
The reason is that heat transmission only occurs in three basic ways: convection (transferring heat into some other substance which then moves away), conduction (transferring heat into some other substance which stays put) and radiation (transferring heat as massless particles, usually light). Since empty space doesn't contain any "other substance", the first two don't work, and the third is much slower.
Down here on Earth, the main way we transfer heat is through convection, from our body into the air around us. Again, the problem with doing this in space is that there's nothing to transfer ''to''. (This actually makes space a very good insulator; consider the vacuum flask, [[BrandNameTakeover popularly called a Thermos]]. ''Cooling'' is actually the biggest difficulty in designing modern spacecraft.) The only way you can get colder is by transferring heat into another object (say, by applying your face to a handy asteroid) or by [[http://en.wikipedia.org/wiki/Black_body radiating it out into the vacuum]]. Heat exchange through radiation is a fair bit slower. [[note]] "Fair bit" can be tricky. A human with surface area 1.5 meters squared, an emissivity of .85 and a skin temperature of 300 K will emit 3000 joules in five seconds which is akin to walking out naked towards the south pole on its coldest day. Using information from [[http://www.engineeringtoolbox.com/human-body-specific-heat-d_393.html here]] and a few simple assumptions seen [[http://www.google.ca/#hl=en&safe=off&q=3000+J+%2F+5s+%2F+%283470+J%2Fkg%2FK*60+kg%29+in+K+%2F+hour&aq=f&aqi=&aql=&oq=&gs_rfai=&fp=f5d0e3cd46a35ba9 here]], you'd lose about 10 degrees Celsius (18 degrees Farenheit) per hour. The reason we don't feel this tremendous heat loss ordinarily is because we are ourselves receiving a comparable amount of black body radiation from the matter surrounding us. Assuming this person is in space near the earth and has half their body facing the sun, they are also receiving about 500W of solar radiation, roughly the same as the 600W they are radiating. [[/note]]
Changes in the temperature of an object in a vacuum depend on whether it radiates more energy than it absorbs from cosmic radiation. This means that a human body in interstellar space ''will'' eventually freeze, but it will take a very long time; in the hundreds of hours. Closer to a star (or other energy-emitting NegativeSpaceWedgie), an object in space is likely to ''gain'' more heat than it loses. (A more in-depth discussion of the role of radiation in all this can be found on the [[SpaceIsColdDiscussion Discussion Page]].)
Partly, our nerve endings detect the contact of air and water molecules with our skin; our brains perceive differences of energy at contact points as hot or cold -- sometimes painfully so -- but this is not a factor in space. Since another significant part of what makes things feel cold is how fast we are losing heat - just compare touching metal and wood at the same temperature - this means space wouldn't feel ''that'' cold.
However, the idea that anything exposed to space will instantly freeze has ''some'' basis in reality, though for different reasons. Since there is no pressure in a vacuum, the boiling point of water will plummet, causing any water to immediately begin boiling (the boiling point of a liquid is dependent on the ''pressure'' around it). Since some extra energy is needed for water to change from liquid to gas (aside from the energy needed to reach the boiling point), it will sap a little heat from anything it happens to be in contact with. This evaporative cooling will likely cause some freezing on a person ThrownOutTheAirlock -- the eyes and mouth, for instance -- but will just make their death slightly more unpleasant (and blurry), rather than instantly turning them into a HumanPopsicle. [[note]] Misinterpretation of that last point has led to the oddly contradictory but still widespread belief that your blood would boil in space. In truth, the blood inside your body would remain at a high enough pressure to keep it liquid. It would boil if your blood happens to be ''outside'' your body when you're spaced... but, if it is, frankly you've got larger problems to begin with.[[/note]]
Now, it is true that any object found floating in space is likely to be very cold indeed -- it's likely been out there for a while, and radiating its energy away until it is about even with the local background count; touching it would be a bad idea. But space itself doesn't act cold, in the way so often portrayed.