Google News offers an interesting ability to search through a number of newspaper archives for stories and advertisements. I went ahead and did a simple "Tolkien" search for a relevant timeframe (1930-1972) just to have some fun. The article titles and snippets are useful, and the graphical interactive timeline (seen above) is entertaining. The downside is that most of the archives are using a "pay-per-view" model - for example, that 1965 New York Times article will set you back $3.95 if you want a digital scan of the entire article or just a text copy.
The good thing is that there is enough information in the free abstracts to make a good guess if the article is useful or not, and if you are under a very tight budget, many of these newspapers are available at a local library (or library exchange program) on microfilm. The oldest newspaper scan is from June 1753!
Also, most of the recent articles (I spot checked the last few years) are directly linked to the websites of the newspapers, and the full articles are accessible for free (until Rupert Murdoch puts up a pay wall, at least).