Actually, most stock coolers have thermal pads instead of thermal paste. Paste will work better than pads by usually 3-5 degrees. The pads are ridiculous! I scrape it off ASAP and put on paste when I get a new processor.
You can get paste at most local computer shops. NewEgg definitely has it. I suggest Arctic Silver 3...but be warned, when you put the paste on, it voids the processor's warranty.
-Lasereth