Hi IBIubbleTea :wave:
Yep, you'll need to remove all trace of the old stuff from both the top of the CPU and the bottom of the heatsink. The bulk can be scraped off with a thin plastic something, a dead credit-card or equivalent is ideal, then use Isopropyl-alcohol or acetone to remove the rest.
You can use cotton-buds (Q-Tips) to remove the remaining residue, but any natural (not man-made, like nylon, rayon) material will do, I've found that an old bit of denim works very well.
'Arctic-Silver' is amongst the best pastes going, along with 'Tuniq TX-4'.
If you need them, there's plenty of short video-tutorials on application, on Youtube :wink: