Several ways, but I find it easiest to:
Cut out the watermark and put it on a layer above a background of the same frame aspect ratio as your output. 4x3 for normal TV. Background must be at least as big in each dimension as your video for best results.
Reason for 4x3 is that PhotoShop (pre CS) works in square pixels. Premiere will recognise this and do the necessary scaling to non-square pixels automatically. If you use the DV frame size, you'll get geometric distortion unless you use PhotoShop CS and opt to work in non-square pixels in PS.
Position and size the watermark in the frame to avoid having to do unnecessary manipulation in Premiere.
Name the watermark layer so you can identify it and save in PSD format.
In Premiere, import the PSD and choose only the watermark layer.
Drag the watermark onto V2 or up and check it has Alpha Matte or White Alpha Matte transparency.
You should then be able to see the watermark superimposed on the background using ALT-scrub, by rendering, or using any RT facility your system might provide.
Hope this makes sense.
There are some great tutorials on this and other aspects of Premiere at