Yes, as mentioned you need to CAREFULLY
remove the CPU from the heatsink. After that, you need to clean BOTH
the CPU heat spreader and the bottom of the heat sink with Q-tips and high purity isopropyl alcohol (that means look for the label with the highest % of isopropyl alcohol.) You can find isopropyl alcohol at your local grocery store near the rubbing alcohol & Hydrogen Peroxide, for about $1.00 or less.
I put a bit of the iso. alcohol into a small plastic dixie cpu, and clean that way so that I am not getting junk into the entire bottle.
Once it is clean, put on new thermal paste, and simply re-apply the heatsink.
here is a guide for refernce, just click on the CPU you are working with...
Arctic Silver Incorporated - Route to Product Instructions for Arctic Silver 5