That was my favorite go to hike when I lived down in Madison. The best section is between the Hwy 12 trail head and the head quarters up by 59. It's a little rough to get 3 days two nights out of it unless you're doing short days. The section above 59 to the end isn't quite as nice. A lot of it is crossing open field and there was a large burn area but that was about 5 years ago. The wooded sections are nice but you skirt close to the highway. The last couple miles in the Scuppernogg are nice and the last shelter up there is fantastic. I believe you do have to camp at the shelters in the park, they don't allow wilderness camping. Water can be tough to come by, the only place you can really count on it is at the Horseriders camp. Also most the trail crisscrosses with the horse trail so you have to pay attention some what. Definitely stop at the stone elephant and leave some tobacco. :) All in all its a gorgeous hike. If you can get to the northern unit it's a bit larger so would be easier to get 3 days out of it but it's definitely doable in the southern unit if you're willing to do the whole thing.
EDIT: I should have said the only place you can count on water is the small section between the horserider's camp and the headquarters. There is also water at the Emma-Carlin bike trails trailhead. But those are all so close together it's not much help on the rest of the trail. The section between hwy 12 and the horse riders camp is where it is the most difficult to obtain unless you're willing to filter dirty water.