How does a heatsink on top of a CPU, which is hot, cool down your CPU? A heatsink can be stuck on your CPU to cool it down. That heatsink feels cold when the system is not turned on. However when the CPU is turned on the heatsink is extremely hot. Isn't that contradictory to a certain extent? I expect a heatsink to always be cold and to have the air blowing system turned on for convection purposes.
Could someone explain what is wrong in the way I see things?
 A: 
"I expect a heatsink to always be cold"

The purpose of the heat sink is to transfer heat.  The rate of heat transfer depends in a complicated way on (a) the temperature difference between heat sink and air, (b) the exposed surface area, and (c) the air speed.
The heat sink is at its most effective if it is at the same temperature as the CPU.  This is because this gives the maximum temperature difference between heat sink and air.  This is why heat sinks are often made of copper: copper conducts heat well.
Let us suppose that the CPU is producing heat $Q$ (Watts) and that the heat sink transfer heat at a rate linear with the temperature difference:
$$ Q = K_\text{eff}  (T_\text{CPU} - T_\text{air})$$
where $K_\text{eff}$ is the effective heat transfer coefficient.  Solving for the CPU temperature:
$$ T_\text{CPU} = T_\text{air} + Q / K_\text{eff}$$
So, the CPU temperature is lowest when $K_\text{eff}$ is highest and $K_\text{eff}$  is highest when the heat sink, due it to having high thermal conductivity, is at nearly the same temperature as the CPU.
A: Heat flows can be modeled like electric currents. Temperature differences correspond to voltage differences, and the heat flowing is similar to an electric current. In both cases, the two are approximately linear, and we can define the coefficient as a resistance value.
Now, if the resistance is zero, we'd see that there will be no temperature or voltage difference; if infinite there won't be any flow. Both are of course ideal cases.
So, back to the CPU cooler. The goal here is to move a lot of heat from the CPU to the air. This requires a low resistance - high flow, low temperature differences. But the resistance here has two parts: moving the heat from CPU to cooler, and from cooler to the air. These are of course resistances in series, so they add up. (just like electricity). To minimize the sum, we need to minimize both resistances. And the temperature in between (top of cooler) will be dictated by the ratio of the two resistances.
An engineering observation is that moving heat from a solid to the air isn't very effective. Air has a rather low heat capacity per volume, as it's so thin. Adding a fan helps with the volume of air, but it's going to remain the bigger resistance of the two.
SO, just as two electric resistors form a voltage divider, two thermal resistances divide the temperature. The top of the cooler will be somewhere between the CPU temperature and the ambient air, and engineering tells us it's going to be closer to the former.
A: I'm going to answer this in a far  more general way: You don't make cold, You move heat.
Think about an air conditioner: The bits outside get very, very hot. What it's doing is expending mechanical work to move heat from from the inside to the outside. The heat hasn't vanished and cold hasn't been created, the thermal energy has just been moved around.
Unlike an air-conditioner, a normal CPU heatsink is a completely passive system. It can't directly move the heat but it does provide it a highly-conductive place to go, thus pulling at least some heat out of the CPU. Because of the higher area (and more importantly thermal mass) each unit of heat energy is spread thinner over a larger area. The heatsink gets hot, but without it the small thermal-mass of the CPU would be far, far hotter.
Do note that there are some special computer cases with active cooling. This would satisfy your expectation of a cold CPU Heatsink. The mechanical work from the cooling system creates more waste heat than a simple heatsink with fans, but that heat is being dumped from the system so it doesn't affect CPU temperature.
A: In general, a heatsink should feel hot, if it's doing its job right. If it feels hot, that means it's transferring energy to your hand, which means it's transferring energy away from the CPU.
This also holds for other cooling things. The cooling coils on a fridge or an old A/C should feel hot for the same reason: the heat you're taking away has to be dumped somewhere. If the cooling coils themselves felt cold, your fridge would be working in reverse; it'd be heating up your food.
A: Already good physics answers. Here comes an everyday metaphor which doesn't require as much physics or mathematics knowledge (I hope).
A heat sink should drain the heat of the thing it is attached to. It should be the points or areas which the heat flows towards. That is what a sink is, a point where something flows into. For example a kitchen sink - that is where all the water flows towards and gets sucked up.
Then of course it will probably be even better at doing this if it is also at the same time able to transfer away heat quickly away from itself - the kitchen sink is more effective if it is not clogged up but able to keep the water it sucks up moving so it flows somewhere else.
A: The goal of the heat sink is to improve heat flux from CPU to surrounding air. Heat flow is a function of the area of contact and the temperature difference. By adding a component that increases the area, you increase one factor; but it's worth remembering that the heat sink will have to have a temperature between that of the CPU and the air: if it's at the same temperature as the CPU, no heat flows from the CPU to the heat sink; it it's at the same temperature as the air, no heat flows to the air.
In practice, it's easy to make the thermal resistance between the heat sink and the CPU packaging quite low (note - the chip is typically quite a bit hotter than the package, and it's only the latter that touches the heat sink). So with the conductivity between CPU and heat sink being better than conductivity from heat sink to air, the heat sink will tend to a temperature close to that of the CPU.
A: When a heat sink is in intimate contact with a source of heat, like a CPU, heat is transferred in accordance with Newton's Cooling Law:
$$\frac{\mathrm dQ}{\mathrm dt}=uA(T_\textrm{CPU}-T_\textrm{Sink})$$
Where $u$ is a heat transfer coefficient (CPU to sink) and $A$ is the area of contact between the CPU and the heat sink.
Note that $\frac{\mathrm dQ}{\mathrm dt}$ is the heat carried off from the CPU per unit of time.
Higher values of $T_\textrm{Sink}$, as the basic formula shows, actually decrease $\frac{\mathrm dQ}{\mathrm dt}$, which becomes effectively zero when $T_\textrm{CPU}-T_\textrm{Sink}=0$.
To prevent this from happening, the heat sink itself has to transfer accumulated heat, usually to the surrounding air, in which case another heat transfer equation comes into play:
$$\frac{\mathrm dQ}{\mathrm dt}=hA_\textrm{Sink}(T_\textrm{Sink}-T_\textrm{air})$$
Where $h$ is the convection heat transfer coefficient (sink to air) and $A_\textrm{Sink}$ the sink's surface area exposed to the air. $h$ is very dependent on speed or airflow which explains why forced air circulation (fan assisted ventilation) is often used.
In steady state ($T_\textrm {CPU}\approx \text{Constant}$), we have, with $\dot{Q}_\textrm{CPU}$ power generated by the CPU:
$$\dot{Q}_\textrm{CPU}=(T_\textrm{CPU}-T_\textrm{air})\left[\frac{1}{uA}+\frac{1}{hA_\textrm{sink}}\right]=(T_{CPU}-T_\textrm{air})\frac{1}{K}$$
Or:
$$T_\textrm{CPU}=T_\textrm{air}+K\dot{Q}_\textrm{CPU}$$
With:
$$K=\frac{uhAA_\textrm{Sink}}{hA_\textrm{Sink}+uA}$$
The influence of the various factors on $T_\textrm{CPU}$ can be readily appreciated.
Ingenious ways of increasing both $h$ (apart from forced circulation) and $A_\textrm{sink}$ to lower $T_\textrm{CPU}$ have been used like cooling fins or this design (ST-HT4 CPU Cooler Riser):

The highly heat conductive copper bands mostly release the heat from the U-bends.
A: everything is relative. while it may feel "hot" when compared to your fingers, i assure you the heat sink is still colder than the cpu itself. moreover, the heat sink's job is simply to move heat from the cpu into the air. as such, the temperature of the heat sink is not important as long as the heat flowing thru it is sufficiently high. the heat sink is an improvement over a cpu-to-air interface because heat flows more quickly both from the cpu to the heat sink and from the heat sink to the air. conduction from the cpu to the heat sink is faster because the heat sink is a better conductor of heat than air.  conduction (and radiation) from the heat sink to the air is faster because the heat sink has a larger surface area.
A: The key here is conductivity, which is simply speaking the speed at which heat moves to/from the object. Objects feel cold or hot not based on merely their own temperature, but also their ability to radiate or conduct that temperature to you. In essence, something only feels hot if it succeeds in warming up the part of the body you're sensing with. The same with cold, it has to result in your body cooling down and actually being cold.
Plastics are notorious poor conductors and respond slowly to heat changes, whereas metals are often good conductors, feeling cold to the touch when cool (they conduct the heat away from your fingers efficiently) and resulting in burns when hot (fast movement of their contained heat into your fingers).
Why are good heat sinks conductive? Well, a heatsink wants to do 3 things: firstly absorb the heat away from the CPU, then move that heat away from the CPU, then finally radiate that heat into the general environment, and it needs to do these things at a rate that reaches equilibrium with the rate heat generation of the CPU at an acceptable effective temperature. In all these cases, conductivity is conducive to these goals.
