In April I rode the Natchez Trace from Tupelo to Natchez, and then the Mississippi River Trail to Vicksburg. I know that store well!!
I preferred the non-Trace riding better. The MRT route goes through amazingly beautiful country. I found the Trace a bit boring after a few days, but still it was a nice ride.
We saw very few other cyclists. I guess April is a bit early for the big cycling season.