I have never EVER seen a sticker on the CPU. Rubbing Alcohol (70% or better) works very well in cleaning it. Just make sure its dry before doing anything else.
Applying the paste without cleaning wont hurt anything, but it is a good practice, just incase.......
Cheers,
-PM