The short answer is that it didn't. Monarchies did not become more common, and Europe in general did not adopt absolutist rule, immediately after the fall of Rome.
First, to answer your literal question, monarchies were already common before Rome fell.
Given above, therefore, most of Europe were already governed by monarchies even before Rome fell. In fact, the establishment of the Roman Empire converted large swathes of Southern and Western Europe into monarchical rule.
Note that while much Italy and Greece had previously been oligarchies or democracies, most if not all originally had kings, such as the Roman Kingdom or Athenian Kingdom. Some even retained their monarchies until the Roman conquest, for instance Macedonia or Syracuse.
Your implicit question seems to be why Europe became governed by absolute rulers. That's a misunderstanding; monarchies are not necessarily absolutist. The kingdoms of Early Medieval Europe were mostly set up by Germanic peoples in the wake of Rome's fall, and consequently inherited the Germanic kingship of their earlier tribal governments.
While the specific varied, these kings primarily acted as military commanders and judges. Vestiges of these roles remained apparent today - all British criminal prosecutions are brought in the name of HM Elizabeth II, incidentally commander-in-chief of all British, Canadian and New Zealand forces.
In fact, up until the High Middle Ages, the power of kings were severely limited. Feudalism jealously guarded their power against royal overreach. The authority of early Kings of France were largely confined to Paris, while as late as 1215 the barons of England would force their king to agree to the Magna Carta. Scandinavian kingships retained their elective character into the Late Medieval Period, and the throne of Germany remained elective until the dissolution of the Holy Roman Empire.
All in all, absolutism did not really prevail in Europe until the Early Modern Period (even then, only briefly and to uncertain degrees).