^I believe the conceit of the series is that in its alternate history, Texas has expanded to incorporate New Mexico and other states.
Though, it should be pointed out that New Mexico's history and eventual statehood was completely independent of events in Texas. Actually, it's more likely that, had events transpired the way they did in the book, New Mexico would be the larger state that incorporated most of Western Texas.