Any particular kind of CPU?
Run the system on full load for an hour or so before taking off the heatsink, this will make it easier to take it off. When I haven't done this, I have often taken the CPU out of the socket - when it is locked in place - when taking the HS off.
What you have to do, unclip the heatsink and lift it up vertically. You will then see your CPU in its socket. Lift up the little clip and gently take the CPU out. Put the new CPU into the socket and close that little leaver.
Now to clean the heatsink, get some isopropyl or 90%+ alcohol liquid and dip a cotton wall bud into it and clean the top of the heatsink until there is no grey thermal compound/pad - the pad needs scraping off with something like a old credit card. when this is done put a blob of AS5 or other thermal compound onto the CPU, do not put any more than half a pea or a grain of rice in the middle. then put the heatsink on. Do not let there be contact with the thermal paste and lift. If you do that you need to clean the CPU and heatsink again with the isopropyl. Attatch the fan header to the motherboard and boot into windows. Simple.
Cisco CCNA, Comptia A+, 1/3 through CCNP