The BrickLink Catalog, which is the most comprehensive database of LEGO parts ever made, lists the first official stickers from 1971. They were used in the Homemaker sets to decorate furniture, etc. List of LEGO Stickers Sorted by Year
Interestingly, at the same time (early '70s), the large Homemaker figures had printed faces, but the first minifigures (with no movable legs and arms) had blank faces, and stickers for their torsos.
To find the oldest printed piece, I went through the BrickLink Color Guide, and looked at the colors that have been produced the longest (since 1950). I checked each of these colors, sorted the results by year released, and looked for the first appearance of printed elements.
The first printed pieces that show up are a large selection of street signs and lettered signs produced in 1955. They were mostly printed on white elements, but there are also some printed yellow and red pieces through the 1950s. First White Printed Parts Sorted by Year
In summary, the first decorated parts were printed, but LEGO has been using a combination of stickers and printed pieces since the early 1970s. While this has been the cause of frustration for LEGO fans and collectors who prefer printed parts, it is actually in line with the policies of other toy makers. Mega Bloks (now Mega Construx), Kre-O, Oxford, Playmobil, etc. also have been using both stickers and printed elements in their toy lines.
It's also interesting to note that in the 1970s and 1980s, LEGO released ideas books with sticker sheets, which allowed children to customize their minifigures and other pieces in creative ways. Stickers were considered cool back then, and were extensively used for customization. Nowadays, stickers are viewed more as a sign of a company being cheap and lazy.
It's worth looking at the history of stickers and printed parts through the years and through toy lines, and how they were perceived and used by consumers (especially children). This is just my personal observation, but I believe the recent preference of printed parts has to do with collectors getting interested in children's toys and demanding what they perceive as higher quality. Children who are old enough to manipulate stickers, generally prefer the customization options stickers provide.