Thermal pads are the easiest to put on. Good pastes provide better heat transfer. Cheap paste is worse than the pads. Get whatever the latest version of Arctic Silver is (5 was the last I got). It's expensive compared to others, for the amount you get, but one small tube will last for several uses. It's also the most effective.
Some tests indicate the differences between cheap paste and the expensive stuff is very small, while others show that it's quite large. Considering the minor expense, it doesn't hurt to get the good stuff, which if nothing else will last longer in use, not drying out and becoming more of a hindrance to the heat transfer.
Yes you need to scrape the old pad off. Pads are one use only for the most part. Sometimes the pad is a lot larger than the CPU die, so there is plenty of unsquished pad left, but scraping that off to where the die sits makes for a poor physical interface. It does work, I've done it, but it's not the best for long term and not having to worry about it.
Rubbing alcohol is a good thing to use to clean the heatsink, although naptha or acetone are a little better in my experience, just more toxic to use. Let the cleaner soak into the pad a bit, then start scraping with a razor blade. Make sure not to gouge the heatsink if possible, as that makes the contact with the CPU worse, although it would take a lot of gouging to make it useless, unless the gouge resulted in a projecting point of metal so that the heatsink didn't actually sit flat. Just scrape it straight across with the razor until you get the majority of it off. Then just use paper towels and the cleaner to scrub the rest off. If you use naptha or acetone, do a couple of rinses with alcohol at the end to make sure it's as clean as possible with no chemical residue. If you've got some lint-free cloths around, or even some old t-shirts you can use for rags, that's a good thing to use for the last wipedown.
