To show how these formation are created, I've documented the making of the Natural Arch.
First I stacked a bunch of thin blocks to get a very rough shape. I glued all the blocks together in the middle with hot glue. Then I drew a rough top view on the top of the block.
I cut the whole block on the band saw.
Next I carved and smoothed out corners and edges using the same kind of tool shown in the photo in the post above.
Then I carved out the indents and details, and later took a wire brush and carved some subtle horizontal lines. Also, I hit it with a real rock to give it a little bit of that rock texture.
After that, a layer of paint should seal it up.