Here is an example of using the same theme as you original choice. Keep in mind that there are a number of steps to follow in their tutorial including cutting up the image into 4 slices, etc. It is some process, but will produce a nice result.

http://www.alaskahandmadejewelry.com/

Have not looked into how bluemarine is set up. Some themes have a built in color selector. If not, one can just recolor all of the graphics that are built into the theme. Using PhotoShop or another graphics program will usually produce good results provided that the author of the theme used graphics for the look of the site.

Or you could luck out and find that all of the color choices are available in the theme's CSS. Just change out the required items for a color change.