You might take a look at PHPThumb. I can't link to it because of low post count. Google the term for a download at SourceForge. The cool thing about PHPThumb is that you can do a ton of different things with the pictures. Not only can you add watermarks but you can change the size of the picture on the fly based on your needs. That is the only script I have had direct experience with. Otherwise there are a ton of different scripts that can do it though, many of them might be overkill if all you need is adding watermarks. One problem with "on the fly" is that the changes are not permanent. If someone knew what was going on they could track the image down and download the non-watermarked version (unlikely for most people though.)
Heres another but you have to pay for it though ($25) http://www.scriptsjoint.com/watermarkscript.php