Ankylosaurs were a group of herbivorous dinosaurs that were covered with bony armor composed of osteoderms (bones formed in their skin), much like the mammalian glyptodonts. Many of the ankylosaurs had osteoderms flanking the tips of their tails, making a club-like structure that may have been used to ward off predators or compete for females.
A recent paper  by ankylosaur expert Victoria Arbour showed that these ornate creatures appear to have evolved these club-like tails in a two-step transition.
Scelidosaurus 199-191 million years ago*
Before talking about ankylosaurs, it’s first important to mention Scelidosaurus, a precursor of sorts to the ankylosaurs. The earliest dinosaurs were bipedal, but Scelidosaurus was quadrupedal, walking on all four legs. Also unlike earlier dinosaurs, Scelidosaurus possessed osteoderms, although not the large, fused types characteristic of ankylosaurs.
Gastonia 127-124 million years ago
After Scelidosaurus disappeared, the ankylosaurs appeared in the fossil record. They had much more elaborate osteoderms that had fused into plates and spines. The earliest fossils, such as Gastonia here, had flexible tails, often flanked with spikes, but lacked the mallet shape characteristic of later species.
Gobisaurus 93-90 million years ago
Gobisaurus differs from earlier ankylosaurs in that it had a very stiff tail, achieved by having highly overlapping vertebral joints. These fossils have not been discovered with the tail clubs characteristic of the latest ankylosaurs, such as Euoplocephalus (78-77 million years ago) shown below:
This suggests that a stiffened tail, which would have been strong enough for striking predators or opponents, predated the clubs of later ankylosaurs. The clubs then appeared at a later stage, presumably to amplify the power of this putative weapon.
To further illustrate this transition, here is a diagram created by Victoria Arbour**:
*Dates are estimates from fossil distributions reported in figure 4 of Arbour et al. 
**Note that she highlights different ages than I, due to her summarizing of multiple fossils
Questions for Creationists
What happened to the ankylosaurs? Why does the fossil record appear to record a transition from dinosaurs that were bipedal and lacked osteoderms, to quadrupedal species with elaborate osteoderms and club-like tails? Is it a coincidence that these species appear in this order?