With Photoshop CS3?

Normal black border:
create a new layer -
ctrl+a -
Edit<Stroke - choose how many pixels you want

It doesn't work.
Look:

Create a new layer - to get a clean layer.
Ctrl+A - To select it all, there will be a black and white line going all the way around.
Edit>Stroke 1 pixel REMEMBER not to put it on outside but on CENTER or INSIDE.

I hope it works this time

If you want a fancy boarder you can expand your canvas size and work on a new layer.

Do it like this if you want to have a rectangular border all around your image, if you have a "popout" one or whatsoever which is either not rectangular or not touching the outside of your canvas, in Mac command+click the thumbnail of your background layer and do the above