A little clarification my and Marks' post, as the different routes can be a bit confusing:

From Cairo via Bahariya, Farafra, Dakha to Kharga is straight forward, one road only. From Kharga you have two options:

1) You can go north towards Assiut. There is a recent desert road that runs along the west bank of the Nile from Assiut to Cairo via Fayum. I was referring to this one in my post, it joins in to the Kharga - Assiut road about 10kms from Assiut city. Of course you have the option to go along the Nile valley road (convoys only), or the other desert road that runs along the eastern bank of the Nile. From what I've heared, no escort on some sectors of it, but these things change monthly.

2) You can go south to Baris (in the Kharga depression) from where a good road leads to Armant, south of Luxor. The rules for this road keep changing, sometimes free to use, sometimes closed altogether, sometimes only permitted from Kharga to Armant, but not the other way. (don't ask why...) As Mark said, from Luxor you have the option of going north along the Nile to Cairo (eventually reaching Assiut and chosing any of the three options in 1)), or going out to the Red Sea coast via Qena. All options out of Luxor involve mandatory convoys and escorts.