According to FilmPosters.com, taglines originated in the 1910s:
From the very beginning movie posters were a part of commerce, designed to get patrons to the box office. In 1890 a Frenchman named Jules Cheret is credited with producing the very first movie poster, a lithograph designed to promote a short film entitled “Projections Artistiques”. Five years later, a movie poster for the Lumiere Brothers’ “Arrival of a Train” in 1895 was the first to depict an actual scene from the film. However, up until the early 1910s, the majority of early film posters were nothing more than simple “broadside” style signs with little more than block text. A typical poster for an early Edison film contained little more than the movie’s title and the words “Another Edison Photoplay”.
This situation changed rapidly with the birth of the Studio System, and by the mid-1910s such studios as Essanay, Biograph, Vitaphone, Edison and Mutual were each producing their own posters and developing their own unique advertising styles with special border art, title treatment, studio logo, and slogan or “tag-line” to distinguish their quality film from the rest of the pack. In this way, patrons could readily distinguish, for example, between an Edison morality play and a Biograph cliffhanger.
As an aside, it seems the first movie poster was for the Lumières' L'Arroseur arrosé (1895) (and their Arrival of a Train was released in 1896 rather than 1895):
The poster for L'Arroseur, illustrated by Marcellin Auzolle, depicts an audience (in the foreground) laughing as the film (in the background) is projected against a screen. It depicts the moment the gardener is splashed in the face, and is thus also the first film poster to depict an actual scene from a film.
This poster doesn't have the name of the film, so it could be (unconvincingly) argued that "Cinématographe Lumière" is the first tagline.
The earliest I found in IMDb:
The IMP awards has a tagline database, the earliest I found from their poster gallery is one from 1912 and a number from 1913 (follow links to see posters):
- Absinthe (7 January 1913): "Reflective Moments"