The Natchez Trace Parkway is a US National Park that stretches from Nashville, TN south thru Alabama, Tupelo & Jackson Mississippi to Natchez, MS. It is 442 miles long. We went south from Nashville and our stops were set up to use the US Parks campgrounds(they are free). We only used one commercial campground(cost $10 for the three of us) at mile marker 123 Ratliff Ferry. There are towns all along the way, but the Trace does not go thru them. They will be 1-4miles off the road in either directions. All the camgrounds had good water, except Rocky Springs(had water, but tasted terrible).
The ride is hilly, but beautiful. Traffic is extremely light except around Tupelo and Jackson MS. Try to go thru them not during rush hour. Road is great the whole way except in Jackson. They are rebuilding one of the Trace bridges and you have to detour.
This book helped tremendously "Bicycling the Natchez Trace" by Glen Wanner. It has all the towns, telephone numbers, and interesting points along the route. I even carried it with me. Another useful book was "Guide to the Natchez Trace Parkway" by F. Lynn Bachleda. I provides the answers to questions the other book does not cover.
These web sites also helped a lot:
Also the US Parks Service has a packet for cyclists they will send you with a super map and campsite locations and phone numbers.
Hope this helps, if you have any more questions , please ask.
I know you will enjoy the trip. The Katy Trail is next for me in October.