Wrestlefox,
Interstates may at times be your only option for riding and they are fine for those ocassions. I always check the laws in a state before I ride their interstate roadways, I am not convinced that the "east of Texas it is illegal" statement is correct. I would also encourage you to look at the Adventure Cycle routes as you do your pre-trip planning. I often do not follow their exact routing, but it is a good place to start. Also some of the touring companies publish thier routing with enough information that you can get some ideas as well.
As a young man you may not need as much focus on training as your elders do. But, don't forget that the pre-trip planning will take you a lot of time unless you buy the Adventure Cycle maps and follow them.