Question: When did Jews begin to post Mezuzot?
Answer: Based on citation within the text of the Torah, the Five Books of Moses, dated as early as 1230 BCE, in the book of Deuteronomy, Jews were instructed to write "these words" on the door posts/lintels of the homes.
Certainly I would imagine that posting mezuzot was already being practiced in the ancient Biblical monarchy. We have numerous examples of mezuzah niches from the time of the early Second Temple and later.
While we may not all agree anthropologically "why" the mezuzah became an institution apart from Torah commandment, nonetheless we would agree that it is one of the earliest Jewish observances.