Select your rectangular marquee tool, and drag a square across the image, the right click inside the square, and select "Stroke". Select the size ( in pixels ) of the border you want, and the color, and mess around with the blending options if you'd like.
(Note: If your going to change the blending options, create a border on a new layer.)