Hi there. While I personally have never come across any tutorials on this topic, I think I can offer you at least a couple of tips since I usually create some sort of decorative borders for my maps with PS. A lot of the things you can find in that Arsheesh tutorial you posted are valid with PS too; while the tools and commands used may vary a bit, the basic idea is the same: a good border consists of multiple layers all put together to accomplish the wanted look.
I'll give you a quick rundown on how I usually make my own borders, hopefully you'll find at least something useful in here.
There are two things that are my best friends in this task: the Custom Shape tool (found under the Rectangle/Line tool, fast key 'U') and the Layer Styles panel.
The very first thing I'll do, is by making sure I have my Ruler on view, and then lay down some Guides in order to make sure my border is going to be evenly postioned from every direction (see the attachment in case my wording is unclear.)
PSguides.png
I'll start with a background layer. I usually I do this with simple rectangle shapes, by first deciding what size and what shape I want my border to be. I'll make the shapes, and merge them (or if I am uncertain on whether or not I want to make some changes later, I'll at the very least sort these separate shape layers in a folder, so they'll stay in order). I'll open the Layer Styles panel on the layer/folder, and give it a basic Color Overlay in whatever color I see fits the map. I'll leave it at this, for now.
Then I'll set out to creating the decorations. It can be anything from simple lines to the checkered pattern Arsheesh suggested to elaborate drawings. I usually opt for abstract curves, celtic knots or something like that. I'll make the decorations either by drawing them freehand with a Brush, or by using some Custom Shapes, or importing them as a PNG or SVG if I have something I have previously made that I want to use instead. This the most time consuming part, and I often end up spending several hours at trial and error until I find things that look good together. This really comes down to personal taste. At this point, I'll be working with just basic black color.
Once I have the decorations I want, I'll start playing with the Layer Styles panel. There really is no right answer to what I want to use here - it all depends on the look I'm going for. If I want to make the decorations look like they are carved into the border, I'll want to give them a Color Overlay in a hue that is very close to the backround layer's color (or optionally just drop down the Layer's Fill level to something like 10% or even less), and add an Inner Shadow. If I want to give the decorations a painted look, I'll instead give them a dark, ink-like Color Overlay and then give them an Outer Glow in the exact same hue (make sure the Blend mode is set to Normal), in order to give it a blurry look that often helps it 'bleed into' the texture of the map.
When I have found the look I want for the decorations, I can either go back to editing the Background shapes (perhaps experiment with Bevel & Emboss for a more 3D-ish look, or see what a Pattern or Gradient Overlays could accomplish), or then create a lineart layer on top of everything. For the lineart layer, I'll usually draw freehand lines to surrounding the border, and maybe add some extra lines here and there for a more fancy look. I usually only go for this if I want to make my border to look handrawn - freehand is often the only way to truly accomplish this look, but if that is not the goal, simly adding a Stroke to the Background of the border can get you there faster. If I go for a handrawn separate lineart layer, I'll again add an Outer Glow in the exact same color as the layer itself, to get that blurry look.
This is very simple breakdown of how I usually work with these elements. In practice, my borders usually are a combination of 5-10 layers all stacked on top of each other, but they are variations on these basic elements. The key to this all really is the Layer Styles panel. Sky really is the limit here - there really is no limit to what you can do with this baby once you get the hang of it.
Hope this gives you at least some ideas!