A bit more geology that makes sense in a timeline:

2500 million years ago (mya) the oldest known rocks in Kakadu are formed as granite intrusions in the earth’s crust.

2000 mya erosion of earth’s crust exposes the granite.  Faulting of these rocks forms a wide shallow depression (called a geosyncline).

1870 to 2000 mya high areas erode and layers of sediments (some sources say shallow sea filled the geosyncline with sediments), 10km thick, are deposited in the geosyncline. 

1860 mya the weight of the sediments causes depressions in the earth’s lower crust and mantle making it unstable.  This leads to intraplate mountain building.  The pressure and the heat fold and metamorphose (change) the sedimentary rocks (into gneiss and schist).  Because the earth is being stretched and pulled new granites intrude into the rocks.  Faults in the Earth’s crust also open up forming rift valleys in southern Kakadu and volcanoes fill them with lava and ash.

1750 mya the volcanic rocks are folded and eroded by high-energy rivers into a low rugged landscape with jagged upturned ridges.

1650 mya flash flooding from a large river system deposit a 1 km thick bed of sand and gravel, from an unknown landmass to the north west, over the entire area.  This was followed by a long period of erosion in an arid climate resulting in a desert like landscape with scattered low ridges and hills.

1000 mya The sediments consolidate to form the Kombolgie Sandstone Formation mentioned previously.  This is the hard rock that forms the Arnhem Land Plateau.  The sandstone is often ripple-marked and cross-bedded.  There is also a basalt layer near the top of the formation so lava must have also flowed at some stage.

1000 to 500mya.  Geological very stable period apart from a bit of warping in the crust.  The warping causes faults and joints in the sandstone to form.  Flowing water carves its way through the weaker joints and faults in the sandstone to form valleys and gorges that are the major features of the landscape today.

500 -140 mya.  A shallow sea covers the area, eroding the older sandstone into sea cliffs (now the Arnhem Land escarpment) and islands of hard resistant rocks (outliers such as Nourlangie and Ubirr).  Sandstone and siltstone containing fossils are deposited over the lowlands.

100 mya.  The seas recede and most of their sediments are eroded away.

50 mya ancient faults in southern Kakadu move again and form local depressions.  Swampy sediments with fossil trees palms laid down.

10 to 1 mya.  The highlands of Arnhem Land and islands continue to erode and deposit sand on the lowlands.

60000 ya the first humans arrive in Australia.  Other sources say 40000 ya so some minor differences (in the big scheme of things) there.

10000 ya called the estuarine period.  Sea invades the lowlands at a rate of 20 - 30 cm a year.

7000 ya sea levels drop and freshwater swamps form.

Some geological evidence.  This is the Arnhem Land Escarpment composed of flood water sands and gravels 1650 mya and formed into sea cliffs 140 million years ago.  Taken at Gunwardewarde lookout.

This is relatively young landscape of Kakadu floodplains at Ubirr (similar to Yellow Water and Mamukala).  Forming within the last 2000 to 1500 years these freshwater floodplains are slowly gathering more sediment from erosion of rocks higher up and deposition during the wet season.

Ripples in rocks at Arnhem Land.  Left by currents of a huge river that deposited the Kombolgie sandstone formation 1650 mya.

Conglomerates at Nanguluwurr provide evidence of large rivers and floods carrying rocks which are deposited where the water movement slows down.  Again part of that process forming the Kombolgie sandstone formation 1650 mya.

These are all pebbles embedded in the sandstone.

This is an igneous intrusion on the South Alligator floodplain, formed from molten rock forced its way up between cracks in the surrounding rocks.  The softer surrounding rock above this has eroded away.