As with most operations in PS - there are often several ways to approach it.
For simple outline frames in black, white or colors, you can enlarge the canvas size, as already mentioned, with the approriate color slected as the 'background' color. If you then select the outer canvas area only, you can use the filters to create a texture in the 'matte' - add noise to give a speckled Canson-paper look, or add texture filters like canvas or burlap or whatever.
You can 'select all' and 'stroke' the edge with black or a color, which gives a hard-edged keyline.
You can also use the Select All/Modify selection/border command one or more times. You just 'fill' the selected border with whatever color you want. By feathering the selection slightly you can get a quite nice approximation of a narrow 'full-frame' black border key-line, with a slightly fuzzy (i.e. natural-looking) edge to the image.
You can increase canvas size, cut/paste your picture as a new layer over an empty white background, and then play with Layer effects to add drop shadows, internal shadows or glows, etc.
There are TIFF images available (for sale) of "photographic frames" that replicate the look of prints made with oversized negative carriers (or contact prints) so that you can see sprocket holes, frame numbers, 4x5 (or Hasselblad) edge notches, Polaroid positive/negative edge processing artifacts, etc. They have an empty image area into which you can "paste" your own picture in Photoshop.
You can also scan your own photo edges if you have a flatbed scanner that can handle film.
If you have a flatbed scanner - you can scan background materials to use as a digital framing material - cloth, corrugated cardboard, cement blocks (watch the scanner glass!), dead leaves, whatever.
Finally - you can combine most of the above effects in sequence. And even drop in a digitized signature and edition number on the matte.
However - don't make the 'frame' so complex that it overpowers the image. It's better to have an artistic photograph in a plain border than a plain photograph in an artistic border.
8^)