Short answer:

People have been telling these stories for as long as there have been people. Military history books appear as soon as there are books.

Discussion:

Popular military history is, arguably, the oldest historical genre.

Even before men wrote, they told stories of wars-- often embellished, but substantially true. Whether you're looking at the Illiad, or the Old Testament, there are plenty of accounts of battles that derive from oral traditions. Long before widespread literacy, "telling stories about battles and heroes" was popular, that's true of the Chanson de Roland, and there's an enormous body of Arabic poetry recording battles.

Some of our very oldest accounts of battles from the Near East come from the 3rd millennium BCE; the Stela of the Vultures depicts in considerable detail the victory of Lagash over Umma. When you look at monuments erected by ancient civilizations-- no matter what civilization you're looking at, warfare is usually an important topic. Sun Tzu's "The Art of War" is 5th century BCE. Egypt's "Merneptah Stela" is 1200 BCE.

In the world of classical antiquity, we've got a tremendous amount of military history, of varying historical quality. Thucydides' "The Peloponnesian War" in an extraordinarily important book, not just for the story it told but for the method of analysis.

Julius Caesar is an innovator in the use of the military memoir as a promotional tool, a work that's intended for a popular audience and which has remained "in print" essentially forever after. We have only a few pre-modern military memoirs; one of the other notable examples would be the Babur-nama, the memoirs of the founder of the Mughal Empire.

The Norse sagas record wars and battles . . . indeed, it would be harder to find an example of a culture which _doesn't_ have these stories that ones that do. Native American and Australasian, South Asian, African and Asian cultures all have their historical and semi-historical warrior heroes.

The middle ages have all sorts of military chronicles, one particularly noteworthy one would be the Alexiad by Anna Komnene, a (largely) military history of her father's campaigns, written in the 12th century CE. Anna Komnene is often considered the first woman who is self consciously "writing history". Of roughly the same period, the Bayeux Tapestry records in considerable detail the Norman conquest.

When did these stories become a popular subject for print literature with a mass audience? Pretty much as soon as printing began and people could read. Looking at incunabula -- printed books before 1500 -- we can find plenty of military history titles. Josephus' "Jewish War" (1480) "Scriptores Rei Militaris" (1493)-- a collection of Greek and Roman military authors, and of course probably the most influential, Vegetius' "De Re Militari"

When did the public start reading them? That depends on when the public in question learned to read, which varies greatly between civilizations. In the case of the West, printing and protestantism potentiate a revolution in literacy, and as soon as people can read, there's a market for war stories. One of the most realistic portraits of war are prints made by a witness to the 30 Years War, the engraver Jacques Callot. His depictions of atrocities in "The Miseries and Misfortunes of War" remain a remarkably brutal popular depiction of war, fewer heroes, more massacres and public torture; compare with Joe Sacco's contemporary graphic novels of war.

There's a huge body of works from Chinese antiquity -- Sun Tzu is the name that is known in the West, but that's just a tiny sampling of a vast literature. Of course, few "ordinary people" in China were literate, so you can argue whether you'd call this "popular military history" -- the same point could be made of Japanese military epics like the Taiheiki.