Get together a bunch of rocky pieces like slopes and triangles. Try to make them grays, blacks, and whites.
Then get either gold or yellow blocks for the sword. You can make the sword with a golden handle and silver/gray blade, but one color is fine too.
Step 2: The Sword
To make the hilt, you need 5 (five) 2x2 blocks, a 2x8 plate (flat block), and a 2x4 block. For the blade, you need 12 (twelve) 2x2 blocks.
Start at the hilt and build up. The only studs left at the end of the sword should be at the tip of the blade. Build the five 2x2 hilt pieces upwards. Then stack the 2x8 plate and 2x4 block on top. Last, you need to stack the twelve 2x2 blocks on.
Step 3: The Rocks
To build the rocks, take your variety of gray, white, and black pieces and build then up in a random way that looks natural (or as natural as legos can get). Make sure to leave a 2x2 space in the middle for the sword.
Step 4: Finish It.
Stick the sword in the stone and tilt it however you like. You now have a sort of realistic sword in the stone.