We're from NC as well (Rocky Mount area) and have made this trip a few times. My wife's brother lives in Baton Rouge so we usually take I-40 out and I-10 back in order to spend a day or two with him. You didn't say how much time you have so I'll just throw some things out with no particular priority. We haven't found too much of interest between NC and TX but are usually in a hurry to get out west so that could be due to our impatience.
Palo Duro Canyon State Park a few miles outside Amarillo is our first real campground stop (Rest areas and/or Walmart prior to that). We typically spend two nights there - good showers, nice hiking trails and, if the outdoor drama Texas is playing, be sure to get tickets for that (written by Paul Green who also did out 'Lost Colony').
If you've never visited
Carlsbad Caverns National Park consider adding this to your itinerary, We like to camp in the
Dog Canyon campground in Guadalupe Mountain National Park which is about an hour's drive from the caverns.
Sitting Bull Falls is nearby and worth a visit if you camp in Dog Canyon (the campground itself isn't much but the location is awesome). Another option is boondocking in Lincoln National Forest or, if you want hookups and showers,
Brantley Lake State Park is good and just a few miles from the
Living Desert Zoo and Gardens State Park in Carlsbad. From here, we spend a night somewhere on
public lands in NM on the way to Page, AZ.
Lots things to do in the Page area. We usually camp at
Lee's Ferry which is the put in point for the Grand Canyon rafting trips. Things to do in this area include a tour of the Glen Canyon dam and definitely the all day boat trip to
Rainbow Bridge National Monument . This campground is also near
Vermillion Cliffs National Monument and the Rock House Road is a great drive unless its wet. Its also about a two hour drive to the North Rim of the Grand Canyon (much nicer than the South Rim in our opinion). Really nice boondocking spots can be found in Kaibab National Forest just outside the entrance gate to the North Rim - Get a USFS map of this NF and make the drive to Point Sublime for a great half day trip.
Finally, we made it to Utah. No doubt on this one - see the Mighty Five and any Utah State Park we've camped in has been great. In the Moab area, if you want a 'developed' campground, Horse Thief is central to Arches NP, Canyonlands NP, Dead Horse Point SP and lots of great trails - Shafer Trail is a must do; easy but lots of dramatic photo ops to impress the folks back home. I'd suggest getting
this backroads guide and
this Grand Circle Guide. I would definitely stay inside the Park when visiting Zion; the traffic getting in can be horrible (two plus hours) at peak times. Site B42 in the Watchman campground is really nice but you will need to make reservations as soon as the six month window opens to get it. 44, 46, 48, 50, and 52 are prime as well and right on the river. Also suggest you make reservations for Capitol Reef if you want to stay at the Fruita campground within the Park. Primitive camping is available at Cathedral Valley and Cedar Mesa. Don't miss driving the Notom-Bullfrog road through the Waterpocket District and the Burr Trail. For Bryce National Park, I'd suggest camping at Kodachrome Basin State Park. Plan to spend at least one night boondocking along the road through the
Valley of the Gods.
Get in touch with the tourism folks on the state websites for AZ, NM and UT and request their info packets. We may be heading that way again next Spring and will get in touch if things work out.
. Seeing the Canyon from Kaibab NF would satisfy that requirement, provide awesome dispersed camping and, depending on route, maybe a bit of an offroading challenge. IIRC, was about three hours from our campsite outside the North Rim to the southwestern terminus of Hwy 12. There is just so much beautiful country in the Four Corners area that there's no way to cover all the possibilities and its easy to become overwhelmed by the options. The biggest negative IMO is, no matter how much planning you do, you're gonna miss something. That concern is more than offset by knowing that its almost impossible to make a bad choice.
