Are there any software that can download videos and then watermark them.. and then upload to youtube, veoh, etc?
You can also use Windows movie maker in watermarking videos.. check out this video tutorial http://www.youtube.com/watch?v=lcdiab_Lfkg Good luck!
Or, for better authenticity, put your name/company/web address actually in the video when you make it - that way everyone knows you didn't just steal it from someone else. On the upside, if you do label stolen stuff with your own name at least the original owner will have all the evidence they need in court.
Another option to have a video player showing your logo on the screen, without use of any video editing software for your each video! check it out: Flash Video Player with Logo