It sounds very easy, but you must change every frame of your video to show a watermark.
The article
Creating a Watermarked Photograph with GDI+ for .NET explains the process for a photo.
So you need to decode, than add the watermark and then recode your video. Quite a lot of work not only for your CPU but also your code.