aftermarket heatsinks usually work better and more quieter than stock stuff..
cleaning the old thermal stuff and reapplying a new layer before fixing your new heatsink is recommended as well.. paste is better than pads, but thats a matter of opinion.. doesn't matter what you use, as long as its applied correctly.
But it depends.. is your current one not performing as well or is it too noisy?
oh yeh.. on last thing.. don't get any old hsf, get one suited for your cpu type/socket and look at its specs if you want acoustically more quieter ones etc.