Bookmarklets
This blog post from ResearchBuzz describes ways of searching for free and legitimate versions of news articles that are otherwise only found behind paywalls. Please note these techniques take a little time and do not find everything.
Chronicling America: Historic American Newspapers
US newspapers 1789-1963, digitised by the Library of Congress. Includes the US Newspaper Directory with information - not text - from a wider date range of US newspapers: 1690 to the present.
Europeana Newspapers
Digitised versions of newspapers from around Europe, from the seventeenth century onwards. 10 million pages in total.
Gallica: French newspapers
Good selection of historic French newspapers.
International News Archives on the Web
Not updated recently, but may be useful for finding news archives from particular countries.
Trove (Australian newspapers)
Search engine for material in Australian libraries, including newspapers. Tick the Available online box and run your search