To your sample: As a bed of sand and mud dries in a swamp or lake, they form these shapes but only for a shallow depth. We have pictures of these by the thousand every day as a result of the drought, as you know. Some time a long LONG time ago (tens of millions of years, let's say), this is what happened in that region - you can see the rock is made of finer material (mud) and sand. Then the dry lakebed was covered with dry sand from dunes, etc, and buried. Move forward some millions more years as the overlying sandstone is now weathered away, exposing the old dry lake bed. Viola - old polygons of stone. Some are missing, I would suggest, simply because someone picked them up and took them away for use as "bush rock" garden path pavers. There are people who do that, you know...
Yes, we have many examples of fossilized mud cracks, and that is one possible scenario. Based on my googleresearch though, these, however, do not appear to be an example of this. They are quartzite, which is a low-grade metamorphic rock that occurs when you subject sandstones to great heat and pressure either because of burial or high temperature gradients associated with volcanism. Essentially, it fuses the grains, making it much harder and less fissile than sandstone, although the gradation between sandstone and quartzite is wide.
Heat and pressure compress (and sometimes partially melt) the sandstone, so much that there if virtually no pore space between the grains. The rock and the cement become one continuous quartz matrix. (Think of how a package of hard candy looks and how they individual pieces stick together when left in a hot car)
But eventually, parts of the sandstone may get exposed by continued erosion. When this happens, the heat and pressure are removed. Cooling causes the rock to actually shrink, but decompression causes the formation (as a whole) to expand. When that happens, the rock fractures. Fractures now fill some of the volume previously occupied by the now shrinking rock. In some rocks, the fractures are very irregular. Most often, fractures occur along and perpendicular to bedding planes, which are natural planes of weakness. However, in extremely homogeneous rocks, most classically, basalt, but occasionally pure quartzites, there are no planes of weakness so the fractures occur almost like crystal cleavage. Fracture occur in
very regular patterns. These fractures can go quite deep into the rock (like the columnar basalts at Devil's Tower and Devil's Postpile), or they may be more superficial. I'm not sure about the Hawkesbury Sandstone, but I suspect you would see those vertical fractures continue deep into the formation.
But the
surface of the now-exposed formation is the part that is subject to erosion, so you will often see widening and smoothing of the cracks near the surface as the edges are worn off by time and the elements, just as you see the edges of the writing wear down on very old tombstones. So it may
appear that the cracks are very shallow. You simply can't see the hairline fractures deep into the rocks.
This truly is a marvelous and rare geomorph, well worth oohing and ahhing over. I'd love to see it myself, and perhaps I'll make it a point when I finally get to Oz. But for all it's beauty and look of being "created" by some living hand, (or rectum) it is easily explainable by natural processes. Sometimes, really quite often, geoscientists disagree on the precise mechanism (just as Zep and I are doing here), but you can be pretty sure that they have plenty of ideas to test before they get desperate enough to throw up their hands and say, "Must be polygonal poop from a supersized silicate serpent."
How did you KNOW? Are you like, psychic, man? 
