I think the reason you have had no replies yet is that there are a lot of ways to do this, and they will all have subtly different results. I'll fall back on my very-semi-pro PS user status and suggest a couple.
Start with your original picture again, use Image>Canvas Size (I think - not got PS on this machine) to make the canvas bigger. Hit CTRL+J to copy the image onto a new layer, then click on the background layer and choose Edit>Fill and select black. Next, choose Layer>New Layer, make sure the new layer is selected and then use the rectangular selection tool to draw a selection on the side of the photo - making sure the selection extends above and below the image. Use the gradient tool to draw a black to black gradient, but set the opacity to zero on the side next to the photo. As this gradient is on a separate layer, you can move it around to position it where you need it. Use CTRL+Z to undo and redraw the gradient until you're happy with the effect. Once you're happy, flatten the image, then use the crop tool to cut the whole thing to size and remove the unwanted top and bottom of the gradient.
Another way would be to use the selection tool on the layer with the image on it, feather the selection, then use the Image>Adjustment>Brightness/Contrast to darken the edge of the image to black.
If neither of those help, there are lost of good tutorials and links to other help websites on
http://www.adobe.com.
Good luck with it.
