I just discovered ProQuest, a library service that provides among other things fully-indexed historical newspaper archives in PDF format through their ProQuest Historical Newspapers:
This database offers full-text and full-image articles for newspapers dating back to the 19th century. For most titles, the collection includes digital reproductions of every page from every issue--cover to cover--in downloadable PDF® files. This ongoing project has already completed The New York Times® The Wall Street Journal®, The Washington Post®, The Christian Science Monitor. The Los Angeles Times® and the Chicago Tribune® are currently going through the digitization process.
You can request a free trial, but your best bet to use this service is to head over to your local library and find out if they have it.
Why isn't this simply available directly on the web? While you might be able to get PDF archives, ProQuest have fully indexed the text and provide a decent search engine over the archive.