I clean it off with the highest grade of isopropyl alcohol that I have (93% I believe?). Usually with a paper towl or sometimes a Q-tip presoaked in the alcohol. This really only matters if you're trying to apply thermal paste to a stock HSF that usually come with their own thermal solution.
Also, it's good to note that removing their thermal solution voids the warranty (from what I remember, if this is different, let me know).
When it comes to application, it depends on what brand you buy. With Arctic Silver, I simply applied a rice-sized bead to the center and used the heatsink pressure to thin the coat out. With my Zalman paste, it came with a brush adapter that I used to apply it along the entire ceramic cover. I really liked this method a bit more and it may be more helpful if you think your thermal paste isn't spreading as much as it should (since dual core processors tend to either have a large die or are composed of two separate dies).
Also, if I recall, heatpads should always be removed if going with thermal paste as heat pads tend to melt and fill in the crevices.