This is a full icon tutorial for Photoshop 7. It should be translatable to other version of PS and maybe to PSP, I dunno. Feel free to modify to fit your image.
Go from
this to this:
1.) Make a new 100X100 blank canvas. Find a picture to use (I'm using
this screencap of Arwen that I found on, well...
Arwen-Undomiel.com). Resize it to any size (I resized my height to 100) and paste part of it onto your base. Move it to the top-left corner.
2.) Make a new layer. Flood fill with color #B7E6F9. Set to Screen, Opacity 50%.
3.) Another new layer. Flood fill with color #040F20. Set to Exclusion Opacity 100%. Merge all layers.

.
4.) Now we're going to add this texture to the icon:

(made by Thia of
Hybrid Genesis. It's cropped to 100X100.) Set to Multiply, Opacity 100%.
5.) Take the eraser tool. I used a hard, round brush, size 13. Erase any part of the texture covering your picture.
6.) New layer. Use an icon brush. I'm using this brush:

(An icon brush by Sae from
Moonlight.) Frame your image, not the icon. Apply it heavily enough so that you can't see through it. My color is set at #664C19. Layer Normal, Opacity 100%.
7.) Now to add text. Color #664C19. I used font Garamond size 14. I typed A R W E N, then rotated it to a diagonal. Layer-Normal, Opacity 100%
8.) More text. Color #664C19. I used Beautiful ES, size 30. I typed Queen of Gondor. Rotated the text and moved it off the image a bit. Later style Normal, Opacity 100%.
There! You're done. Please don't copy this tutorial! O.K.?