The earliest trails were Indian trading trails. The large populations of Indians in the south made trade between tribes very common. Still not easy trails, but wagons did travel them. Many immigrants chose to travel by steamboat, using the miles longer but much easier and in the long run much faster water routes.
Several of my lines came to Texas also from the southern states. One common route before the "big raft" or logjam was cleared from the Red River was to travel up the Red River, across Caddo Lake, and up the Big Cypress Bayou to Jefferson, Texas. My Broadstreet family used this route when they came from Mississippi to Texas in 1861. You should be able to find lots of information about Jefferson, Texas online. There is also an interesting book written by Eric Brock of Shreveport called, "Red River Steamboats" that describes the boats in detail and the routes they took. Most were not the glamorous showboats of movie fame.
When the logjam was cleared by the early 1870s, and the Caddo Lake water level fell making travel to Jefferson by boat risky when possible, the steamboats began to stop at Shreveport, Louisiana. I'm not sure when the train was built, but my Webb family traveled from Shreveport, LA to Longview, Texas by train in 1872. From there they had to use wagons to get to Wood County. They had come from Georgia, traveling first by train to New Orleans, by steamboat up the Mississippi to the Red River and then up the Red River to Shreveport. The boat trip took 17 days because of low water in December, a trip that usually took 4 days. Altogether, it took them close to a month to reach their destination.
I also believe there was a train between Shreveport and Monroe Louisiana during the Civil War. Before that I believe there were wagon trails, which first began as Indian trading trails. My 4th great-grandfather, John Dickson, traveled by wagon in 1858 to Starrville, Smith County, Texas from Bibb County, Georgia. He was supposed to have been in a train of 40 wagons. I understood sometimes they would have to wait days for their turn to go across rivers on a ferry. A traffic jam of sorts.
I have also read that some folks traveled by boat across the Gulf of Mexico to Galveston and then headed north by wagon.