If you are replacing a CPU cooler, then yes you need to remove the old thermal paste and replace it with new thermal paste. A BB size dot in the middle of the CPU is enough.
If you are just replacing a fan then, you don't need to remove the cooler. Just remove the old fan and replace it. The installation varies usually the fans are secured with a spring clip.