I was looking at some of these for video overlay, but have never tried them:
http://www.robotshop.com/ca/en/video-experimenter-arduino-compatible-shield.html
http://www.seeedstudio.com/depot/Video-Overlay-Shield-p-1232.html
It might be possible to do some overlay directly using just an Arduino, but something like the above would probably be the way to go.