Import the video as a new video layer (Layer --> Video --> New layer from file), add your watermark as another layer, then export the whole shebang using File --> Export --> Render Video. Be aware though, that there are severe limitations in what formats Photoshop accepts, exports and how they are compressed, so you may wish to check out After Effects or other tools...
Mylenium