if the spots are on parts of pic where there are not much details (eg. wide smooth surface, sky, wall, etc), i personally would use patch tool... its a faster method =)
if its on top of many intricate details, then clone tool is the way. but like what shahlan says, the process can be very tedious.