Traveling across the desert by train is a pretty awesome experience, if you have a few days to spare. I started out in Kashgar and simply headed east with stops in various oasis towns along the way until I got to Lanzhou and grabbed a flight.

As others have mentioned, if paying with cash, you should plan on grabbing tickets about no sooner than 2 months in advance (honestly, 2 or 3 days out is probably sufficient).

For awards tickets, you might want to book further out. DL and AA both work nicely with CZ, which has a strong presence in Xinjiang (one of its founding divisions was the Wulumuqi CAAC branch).

ETA: UA miles also work, so I assume other *A does too (maybe for fewer points).