In practice, space is near enough at the temperature of the cosmic microwave background radiation, energy which permeates the known universe at a temperature of about 3 Kelvin, for anything made of normal matter and not 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 K 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 K 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, 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 radiating it out into the vacuum. Heat exchange through radiation is a fair bit slower. 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 Negative Space Wedgie), 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 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 Thrown Out the Airlock — the eyes and mouth, for instance — but will just make their death slightly more unpleasant (and blurry), rather than instantly turning them into a Human Popsicle. 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.