Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
You shouldn't need to replace it unless you've disassembled the computer and removed the heat sink. But if you have, you just want to make sure you clean the old paste off before applying the new paste. Personally, I only use Arctic Silver 5 compound and Arctic's cleaner. All you need is a very thin coating. Any bumps and you want to smooth those out.
 
When ^ says "very thin," just put a glob on that's about the size of a single grain of rice. You can spread it out with a credit card if you want, but when the HS goes back on, the pressure will apply it evenly anyway.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.