You need enough thermal paste to make a good, even contact seal between the cpu and the heatsink. You might
be able to get away with using whatever's left over from your old install if there's enough of it, but I really wouldn't recommend it. It's probably safer to apply a new layer.
I recommend ditching the white gunk most heatsinks come with and getting some of the really good silver paste that has better thermoconductivity. It can make a real difference, especially with modern hot-running cpus. (I seem to remember that thermal paste needs a few days or weeks to "cure" for best efficiency in any case.)
If you're really serious about cooling, you might think about getting one of the top-end heatsinks. silentpcreview has a good list of recommended heatsinks
. I bought a couple of really nice Scythe coolers for my machines and they're much cooler and quieter than the basic ones most people use. They're bigger and more expensive, but it's well worth it.