Stone Texture

1
Start with a new image, 500x500 pixels. Select a dark gray as the foreground color, and a slightly desaturated orange as the background color.

Filter > Render > Clouds

Filter > Noise > Add Noise... Set the noise amount to 3, Distribution Gaussian, and check on Monochromatic.

2
In the Channels window, create a new channel , and select it.

Filter > Render > Difference Clouds

Filter > Noise > Add Noise... Keep the same setting as before, and hit OK.

Filter > Fade Add Noise... 50%

Or, in PS 6+: Edit > Fade Add Noise... 50%

Filter > Render > Difference Clouds Now, keep pressing Ctrl+F to repeat the action, until the channel is balanced with black and white. This may take 2 or more tries.

Double click on this channel in the Channels window, and rename it Stone Map.

3
Go back to the Layers window, and select the layer we were working on before, probably named Background.

Filter > Render > Lighting Effects...

Set the Light Properties to:
Intensity: 59
Focus: 69
Set the Properties to:
Gloss: -100 (Shiny)
Material: 48 (Metallic)
Exposure: -6
Ambience: 4

Set the Texture Channel onto Stone Map, and the height to 100.

Now, tweak the positioning and direction of the light to achieve the desired effect.

Finally, Image > Adjust > Brightness/Contrast... and put both Brightness and Contrast up a bit.

Advanced Tips
a
To engrave text in the stone, go to the texture channel Stone Map, before you do the lighting effects. Use the Type Mask Tool to type some large text. Expand the selection by 5 pixels, then feather the selection by about 5 pixels. Select white and light gray as your foreground/background colors, and go Filter > Render > Clouds. Now apply Lighting Effects to the texture Layer, using that texture channel, and marvel at it's stony goodness. You may need to re-enforce the text shape by typing the same text in black, and laying it over the stone texture layer with 50% opacity, as seen to the left.

b
To make the stone look wet, and shiny in parts, make a copy of the texture layer before you do Lighting Effects on it. Light Effects the bottom layer normally, and then Light Effects the top layer with the Gloss turned up a bit. Then, select the top layer, and go Layer > Add Layer Mask > Reveal All. Then, Difference Clouds the layer mask a few times, and then AutoLevels it. Ctrl+Shift+L