According to this fascinating article, fragrance inserts in magazines -- the scented matte strip that, when unhinged, releases a waft of Coty's Chypre or White Flowers or whatever -- first appeared in in the 1940s, with microencapsulation technology developed by the National Cash Register Corporation (soon after to play a big role in the history of computing).
Looking through old trade journals at the Hagley, I found an example of this technology in use three decades prior to the 1940s, implying that it was first in use in 1910. From the May 1912 The American Perfumer & Essential Oil Review:
I did obligingly smell the circle, but alas, the odor of Rose Aldehyde C has been lost to time and history...