The National Digital Newspaper Program (NDNP), a partnership between the Library of Congress and the National Endowment for the Humanities, is a long term effort to develop an online searchable database of US newspapers. The website for this database, Chronicling America, allows you to search and view American historic newspapers published between 1836 and 1922.
You should definitely give this site a try. Put Natchez in the search box and you get 22,005 results - everything from the 1870 steamboat race between the Natchez and the Robert E Lee to articles about the Natchez Indians. A lot of the results are from nearby Louisiana newspapers, because Louisiana is one of the states that received grants through this project.
Texas was another state that received grants. The Texas Digital Newspaper Project contacted us to let us know they had several Natchez newspapers on their site. The have the Natchez Democrat from December 1876 through December 1878. They also have the Ariel newspaper from July 1826 through June 1827.