Yes the old stuff needs to come off.
Depends what kinda stuff it is. If it is goopy, then I use a damp paper towl and wipe it down., if it is crusty stuff from a stock thermal pad, I use a dry paper towel and it will come off eventually. Some people use rubbing alcohol to aid the process, but I haven't found that necessary yet in my experience. Just make sure not to put too much of the new thermal grease on. Spread a nice even thin layer of it over the heat spreader, OR you can put a small daub (2 grains of riceish sized) in the dead center of the Heatspreader, and let the Heatsink spread it out for you when pressure is applied.