Let's define propaganda as information of a biased or misleading nature, used to promote a political cause or point of view.
One of the more famous ones is Caesar's Commentarii de Bello Gallico, which is an account of his waging war in Gaul from 58 BC to 50 BC. It was probably meant to rally political support, especially from the lower classes, for Caesar. The Latin is pretty easy to read, too, if you are interested in learning the language.
The earliest battle for which we have detailed written descriptions of the events is the Battle of Kadesh (13th c. BCE). It was fought between the Egyptians and the Hittites.
Both sides recorded the events. Both sides say they won.
I think it's fair to say that propaganda is as old as wartime reporting.