If you're talking about the pad on the heatsink itself, yes get rid of that. It does the job, but thermal pastes tend to do the job much better. Scrape off what you can with a razor blade, and then clean it off with some isopropyl alcohol.
Now, it the CPU has pads on the corners, leave those on. They're there to help protect the die from being crushed ally.
Just regular Arctic Silver, not anything adhesive...unless you want to bond the CPU to the heatsink (not recommended---and I think it voids the warranty). You just need to apply it to the CPU die (the rectangle in the center) in a thin coat. It's just to fill in the micro gaps between the CPU and heatsink to get the best heat transfer possible.