Do as Legolas said with the pad, but use the least amount of thermal paste that will give the best metal to metal contact with only the micro sized gaps filled with paste.
Not familiar with the heat sensor but assume you can park it somehow at the edge of the base of the heat sink, making the best contact you can without compromising the heatsink-CPU contact. There isn't a convenient small hole in the heatsink is there like a mini-oven for the sensor?
I imagine that the reading you get first can be useful as a guideline and need only worry if you see a sharp increase in temperature some day in future
Stick the sensor on the heatsink, to the side. Its does give a fairly accurate reading.In my opinion, if its a P4 CPU just use the pad. One advantage of this is that when it comes to upgrading, the CPU will separate from the H/S more easily than using thermal paste which hardens over time.
'Recommended Thermal Paste' To be honest, i wouldn't bother using thermal paste as the pad will do just fine. Built my system 2 months ago and i have had no problems, temp is constant, not low but average.
decide to take off the pad and use paste, you'll have to clean off the sticky muck from the bottom of the heatsink. use a strong alcohol based cleaner. White spirit/turpintine or summat will do just fine.