Piece of cake. I'm not familiar with paint shop pro so i'll explain my procedure for photoshop in the hope that translates
Pretty much my final stage of any image is to shrink it down to the size I want which usually seems to be 800x533 for web posting. After that I run a sharpen action and flatten the image so I have a single base layer called background.
I rename that to Layer 0 and then duplicate it.
Next stage is to increase canvas size by 100 pixels to give me 900x633.
In photoshop that leaves me with the image duplicated in 2 layers with a transparent surround of 100 pixels all the way around.
I select the transparent section of the bottom layer with the magic wand, fill it with whichever colour I want for the border, then invert the selection and delete the image in the centre.
At that point I have a frame on the bottom layer and the image on the top layer so I stick a bevel and emboss plus any other effects I want on the bottom layer to give me my border.
Depending on the image I may also do either a bevel and emboss on the top layer (about 2 or 4 pixels for both top and bottom bevels usually) or alternatively a 1 or 2 pixel stroke using the layer effects. That can sometimes give a nice glow to an image if the frame is dark.
Final stage is to type my name and a title on top which photoshop automatically creates in a new layer. Once that's all done I flatten the lot and choose "save for web". Usually I save @ 90-95% quality depending on the image for jpeg.
Hope that helps.