It might look a bit corny or what-not, but I actually had to do this once(albeit a gypsy wedding). That might not be what you are going to use it for, but i am sure you have an idea of your own.
First of all, we need a video to work with. Again, you can use any video for practice. I am going to put up one of my old 3D videos(as soon as I decide which one).
Just so you know what the end result will be in advance, it is a good idea to get a screenshot out of your video, to use in PhotoShop. If you are using Premiere 6.5, just go to:
File –> Export Timeline –> Frame
Save it, and open that file in PhotoShop. Now, Create a new layer above it. This new layer will be our video’s border.
The stage is set, now make whatever you want for the border. It doesn’t even have to on the edges. For instance, you could add a crosshair to the video using this technique, and use Premiere’s movement controls to make it move around the screen. You could even use any of the interesting brushes in PS to add leaves or grass to the video.
After setting this up, delete the background layer(the video frame), and save the frame as a .psd file(a PhotoShop file), because Premiere knows how to work with .psd files. If you save it as a .jpg file, you might have trouble working with the transparency settings, and some ugly clipping will occur.
Now switch back to Premiere and add your video to the timeline and import the .psd file you just saved in PS. Add the frame in the above track and it should all be set without any more hassle from you. I added the music for which this video was built and my end result is:
I made this frame by coloring around with a blue brush, and later with a red brush, then smudging them, and after that I added the mosaic effect. As you can see, you can add any effect you want. Basically you can use anything you make in PhotoShop in your video. It’s pretty simple, all you need is a good idea(as if good ideas are easy to come by).