This is how I make borders like in my sig:
1) Add a new layer and activate it.
2) Select All (control + A)
3) Select->Modify->Border and pick a value. You want it to be about 2/3 the size of your final border so guess small. I think I used 15 in my current sig.
4) Select the paint bucket tool and click in the border area several times (3 times in this example). Color does not matter
5) Layer->Layer Style->Blending Options and click on Color Overlay. Put it to whatever color you want. You can change it at will.
6) Click on Bevel and Emboss. Under "Shading" click on "Double Ring" (bottom row, third from the left).
7) Leave style and technique on inner bevel and smooth. Increase the depth a lot until it doesn't really seem reasonable. All the way to 1000% works.
8) Play with the size slider until it looks cool.
ta-da