Remove heatsink, remove CPU, clean heatsink with isopropyl alcohol and a lint-free rag/cloth/etc., drop new CPU in, apply thermal paste, reseat heatsink.
EDIT: Whoops, didn't check before I posted to see if it was a laptop.
Found something that might help: http://www.insidemylaptop.com/disassemble-hp-pavilion-dv6-laptop/