IDealy you do not want any of your skin residue to leave behind anyhting on the CPU taht includes the actual surface that disperses the heat where the heatsink sits. This surface has many pits, the idea of thermal paste is to fill these pits and thus creating a impeccable surface for the heatsink to contact. As well as of course providing thermal transfer.
To remove grease from your hands (I also mean skin oil) use fairy liquid before handling components.
Following this I use Arcticclean - http://www.ebuyer.com/product/139175
to clean and prepare the surface of the CPU. I use coffee filters for cleaning as they are lint free and I believe they do not scratch the CPU.
Given your situation I doubt you want to buy anything to clean it however given the fact you have posted asking how to better clean it I would suggest that if you have isopropyl alcohol then you should use that to clean it and a coffe filter - both can be bought for not much expense and can be used for other purposes - the isopropyl has multiple uses for example.
Place it in a ant-static bag once finished and always use a anti-static wristband when handling a CPU, and like dsenerre said DO NOT touch those pins!!!!
Ideally place it back in the original packaging as that wil prevent the pins from getting bent.