It's best you do so, but it's not something that is between life and death. You're not going to kill any components by not doing so, but you'll lower the thermal effectiveness of the thermal grease.
100% agree. It's always a good thing to clean both surfaces and apply new thermal grease. If you don't then you may have air bubbles in the paste which don't conduct thermal energy and create hot spots.
To clean the surfaces wipe with a rough cloth to get as much grease off as possible. Then clean off both surfaces with alcohol. Put grease on the cpu and spread around to cover evenly. Not too much. About a grain of rice size. Seat the heatsink on the cpu chip and give a slight twisting motion as you apply a little downward pressure. This drives out the air bubbles. Clip down the heatsink and you're done.
Oh and make sure you plug the cpu fan back to the motherboard.