How do I clean off my CPU?

I had some motherboard problems over the weekend and had to remove my CPU and heatsink. I have a boxed Intel P4 CPU and heatsink.

I gather that I have to remove the thermal pad that came attached the heatsink because it is now damaged, as well as remove the residue that is on the CPU. What is the best way to do this? And then I will need to apply some kind of thermal paste as well?

Thanks.

I went and ordered some Arctic Silver III. I will be applying this to the CPU and heatsink as instructed on their website (once I get my motherboard back from the RMA).
They say that I need to use acetone or 99% ispropyl alcohol on the CPU and acetone or a xylene based cleaner on the heatsink.
What the heck is xylene? What kind of a store can I find it at? Also, the computer shop in town doesn't sell any kind of CPU cleaner and the drug store only sells 70-80% pure isopropyl alcohol. What is a good place to find the appropriate cleaners for my CPU and heatsink?

Any help is appreciated.