Click the images to enlarge them
Do this first!!!
1) Open a new image that is 8x8 pixels
2) Use the pencil tool (Right Click on the brush tool and selet Pencil".
3) Now, draw a patern like this:


4) Go to Edit -> Define Patern, and just click OK

Now do this
1) Create a new image, or open an existing image you wish to put the border on.
2) Hit "Ctrl+Shift+N" to create a new layer or Layer -> New -> Layer....


3) With the new layer selected hit "Ctrl+A" or go to Select -> All.
4) Now, go to Edit -> Stroke, and apply the following settings, But pick a color of your choice..



5) Right click on the new layer and select Blending Options<br><br>
6) Now tick the box, Patern Overlay and apply the following settings with the 8x8 image you selected.