Why do things cool down? What I've heard from books and other materials is that heat is nothing but the sum of the movement of molecules. So, as you all know, one common myth breaker was "Unlike in movies, you don't get frozen right away when you get thrown into space".
But the thing that bugs me is that things in the universe eventually cool down. How is that possible when there are no other things around to which the molecules can transfer their heat?
 A: If you have heat, you have "random" movement of different molecules in your material.
When two different molecules with different velocity vectors interact, they sometimes emit a photon carrying away some of their energy.
This results in the relative kinetic energy of the two molecules being reduced (due to conservation of energy).
This average relative kinetic energy distributed pretty randomly over the substance is what we call "heat".  The photons that are radiated and not captured again (by colliding with other molecules in the body) carry energy away from the body.
A decent approximation of the amount and spectrum of the emitted photons is known as the "black body radiation curve" for a given temperature.  Here, black refers to "doesn't have a strong unusual absorption/emissions spectrum"; for example, Hydrogen gas has lines in its spectrum caused by the distance between the lowest and 2nd lowest energy state of the electron orbits around the nucleus.
In the local interplanetary medium, there is a large hot heat source 1 AU away (the sun), a few warm heat sources nearby (Earth and the Moon), some teeny tiny far away heat sources (planets and other stars), a low density interplanetary medium that is usually pretty hot (but of such low mass it doesn't really matter), and the cosmic microwave background radiation.
The CMB is at around 3K, and is pretty close to a black body.  So if you are warmer than 3K, you'll emit more and higher energy photons than it will emit towards you.
Your interactions with the IPM is going to be tiny, and won't trade much heat.
If you are close to Earth, you'll get warmed to a few degrees above 0 C by trading photons with it (on one side), while getting nothing on the other.
If you are in sunlight, it will be pouring photons at you.  Heat is a bigger problem than cold quite often due to the Sun in space; we make things reflective or white in order to reduce the amount of heat we pick up from the sun.

Now there are other effects in space.  When air loses pressure, it cools off and water sublimates out of it.  So if you had a room at 20C and 1atm and you dropped its pressure to zero, you could see water forming on surfaces (cooler, less dense air causing water to condense), then as the temperature continues to drop that water could freeze.
Humans will emit gasses and fluids when exposed to space, as our flesh isn't designed to put up with a 1 atm gradient.  The fluids will boil (from lack of pressure) and cool, and that could result in localized freezing; the phase change from liquid to gas soaks up a lot of Joules, and in the grand scheme, 37C isn't far away from 0C.

On Earth, most heat transfer comes from contact.  You interact a lot more with things "touching" you than you do with things far away.  That interaction causes photons to be emitted; if the thing you are "touching" is hotter than you, the photons from their internal interactions and the inter-object interactions will be higher energy than the ones you are emitting in turn.  And, when the high-velocity "other" molecules average velocity with your slower molecules, they'll directly increase in speed (even as they emit photons).
Between the two of those, you'll heat up if the medium in contact is hotter, or cool down if the medium in question is cooler.
Then, the medium you are interacting with, if a gas or a liquid, will have its density changed by heating up/cooling down.  This causes it to stir in such a way that substance with a "more typical" temperature is back in contact with you.  This convection process means that you are quickly interacting not just with the matter immediately in contact with you, but with the matter that is in turn swapping positions with it.
The only matter "in contact" in space is the interplanetary/interstellar medium, and its density is so low that the rate of heat transfer is tiny compared to radiation coming off most macroscopic bodies.
A: You exchange heat with the objects around you.
If the objects around you are hotter than you, you'll heat up.
If the objects around you are cooler than you (neglecting the heat you're generating due to metabolic processes), you'll cool off.
In space, the objects around you (mostly interstellar medium) is cooler than you so you radiate more heat away from you into them than they radiate toward you.
If you were thrown out into space, but very near a star, you might receive more heat from  the star more than you could radiate away into space, and you would heat up rather than cooling down.

But the thing which bugs me is that things in the Universe, eventually cool off, and how is that possible, when there's no other things around, to which the molecules transfer their heat?

There are three main heat transfer mechanisms.
conduction is transfer by direct contact between two bodies, or through a body with a temperature gradient across it.
convection is transfer by the flow of a fluid (liquid or gas).
radiation is transfer by the exchange of electromagnetic radiation. 
Heat transfer by radiation doesn't require any physical contact between two bodies or any material medium surrounding a body. Radiation is the main heat transfer mechanism for a body floating in space.
A: Everything that is not 0 Kelvin radiates electromagnetic energy. In vacuum, this is the only relevant form of heat transfer. The hotter you are, the more energy you radiate (I believe the relevant equation is given here).
The question whether you cool off or heat up in space depends on whether you absorbs more electromagnetic radiation than you give away. So, for instance, if you are orbiting Earth in plain sunlight, you may actually warm up, because there is lot of electromagnetic energy coming from the sun (much of it as visible light).
But if you are in the shadow of the Earth, the amount of energy that comes from night side of Earth and the general direction of the outer space is very low compared the the amount of energy you radiate away at 37ºC, so you cool off and eventually freeze.
A: In the present epoch the universe is a long way from thermal equilibrium. It consists of a large number of isolated hot spots (a.k.a. stars) in a sea of background radiation which has an average temperature of just $2.7$ K.
But stars have finite lifetimes (although this can be a very long time for white dwarf start) so eventually all the stars in the universe will run out of fuel and will cool down until they reach the average temperature of the universe. On very, very long timescales even the protons in stars will may decay into lighter particles.
And the universe is expanding, and cooling as it expands because the wavelength of the photons in the background radiation increase as the universe expands. So eventually the universe will reach thermal equilibrium, when everything that remains in the universe has a temperature just a fraction of a degree above absolute zero.
A: This can be understood easily: If your temperature is higher than the surrounding temperature heat will flow out to the surrounding. It is analogous to electric current which moves from a higher potential to a lower potential. Similarly heat current flows from high heat potential(high temperature) to a lower heat potential(low temperature)
