I am aware that this is quite a wide question and that many factors influenced the development of media (the printing press I presume to have the largest impact) but can anybody give me some examples of earlier use of media to influence others in important situations. As early back as you can.
As far as the modern "mass" media goes this indeed was started after the invention of the printing press like @jfrankcarr pointed out.
But Propaganda has been around since the dawn of human civilization. Even in Prehistoric times there were symbols which could be argued as being propaganda, signs of success or fertility: Venus figurines are a good example of that (However, since prehistoric based on speculation)
Moving on to Mayan society many scientist have argued that the big Mayan temples, which could be seen from afar and rose far above the surrounding forests also served as Propaganda tool to uplift the rulers. (In fact any tall/large structure throughout the ages can most certainly be viewed as a showing success of a society/rules. From the pyramids to the Burj Dubai skyscraper)
The Romans were really good at propaganda. This great long article from the BBC called: The official truth: Propaganda in the Roman empire should give you some great inside about clearly documented 2000+ year old propaganda.
More examples of truly recognized propaganda can be found on this wikipedia page about propaganda as well.
Right from the start in the 1450's the Gutenberg printing press was used to influence people. Not only was the Bible printed but indulgences were printed out in considerable numbers as well. Classical writings, such as Greek philosophers, were also distributed. Within 10 years of the invention of the printing press, it was being used to deliver religious and political messages in books to the educated population. Perhaps the biggest early societal impact of printing was the Reformation. For example, over 300K of Martin Luther's tracts were printed and distributed between 1518-1520.
It was the kind of information explosion and democratization of knowledge that wasn't seen again until the 1990's and the Internet.
Cultural art forms such as group dances, ballets, individual performances where artistes sang of historical or mythological or contemporary heroics existed for a very long time in India. An early reference one can find for this kind of mass communication is that of Ramayana being sung by Lava kusa who toured cities to sing the saga set to music.
Similar art forms and means of mass communication would have existed in many ancient cultures.
Propaganda is an invention of the 20th century. It is the application of behavioral psychology and modern linguistic philosophy that saw rhetoric more widely intentionally applied to other symbols than only language, such as posters, movies, and newspapers. Propaganda was widely used during WWI to improve morale at home and target enemy morale. This is from the seminal work on the subject.
"Propaganda", Edward Bernays, 1912
The systematic study of mass psychology revealed to students the potentialities of invisible government of society by manipulation of the motives which actuate man in the group.
Bernays' main object was to use propaganda for commercial interests. The first forms of propaganda were thus advertising.
The word propaganda comes from "propagation" as in "propagation of the (Catholic) faith." The word first took on a negative connotation when Protestant reformers felt that the Catholic Church was spreading an improper view of Christianity. The concept of propaganda thus evolved over time from the Reformation to the 20th century. John Locke wrote an important rhetorical treatise.
Ancient societies have always spread messages, but this is (applied) rhetoric, not propaganda. The reason is that the messages were not designed for a "mass audience," but would be crafted for very specific audiences. Speeches by Cicero for example were not written to have universal appeal to most of the Roman population. There was no propaganda in the Roman Empire.
Rhetoric is the art of discourse, an art that aims to improve the capability of writers or speakers that attempt to inform, persuade, or motivate particular audiences in specific situations. As a subject of formal study and a productive civic practice, rhetoric has played a central role in the Western tradition. Its best known definition comes from Aristotle, who considers it a counterpart of both logic and politics, and calls it "the faculty of observing in any given case the available means of persuasion."
Interpretations of cultural and artistic art forms are also rhetoric and designed for mass audiences, but are not "applied" rhetorics. Marxist definitions of rhetoric and propaganda will include this though.