[Magnum]

Well, you guys are kinda right, and kinda wrong. Here's how I do it.

To make a regular pixel border:
Make a new layer on top of the background. Fill the whole thing with a solid color. Go to Layer > Blending Options. Turn the Fill Opacity to 0%, then go to Stroke. Pick the color and size you want, and set it to inside.

To make an overlay border:
Make a new layer. Go to Select > All, then Select > Modify > Border. Select half the size of the border you want. Then, use the paint bucket to fill in the border area with a color you want. Click it until the edge becomes solid. Then, change the blend mode to what you want, probably Multiply, Screen, or Overlay. If you want, you can add a stroke normally.