This is a short answer: Rubber stamp brush and healing brush.
Then all it takes is a lot of practice. When in school I had an exercise that was to take an old photograph (scratched, ripped, bent, discolored, dust spots, etc) and digitally restore it back to new.
Another technique involving layers would be to take a section of the image that resembles what you're trying to remove, put it on a new layer, move/transform/mirror/etc and then use layer blending properties like overlay or soft light to blend it back onto the layer underneath it. This technique is used in conjuction with the rubber stamp.
If you look here:
http://personal.bgsu.edu/~aarp/portf...al/2d_023.html at the grafitti on the wall, those were two pictures I had taken. Then using the above technique I put the grafitti on the wall with layer blending and some stamping.
Have fun!