"NO DEPOSIT NO RETURN, NOT TO BE REFILLED," according to some ancient notes
I have, first appeared in 1939.  The source of this information, if it is
to be trusted, is:

Kroll, Wayne L.
  1976  Badger Breweries, Past and Present. Wayne L. Kroll, Jefferson,
Wisconsin.


Other, probably more reliable notes along the same line from Jane Busch's
1987 paper in Historical Archaeology suggest it might appear as early as
1935. Take your pick.

I've analysed the collections of a couple of saloons, and scrutinized
carefully the collections of three others, all dating from the first two
decades of the twentieth century. I'll vouch for the fact that whole
bottles are extremely rare. Almost all of the bottles were broken,
suggesting that the whole bottles were recycled, like Jane hypothesized in
her article.