Cairo to Nairobi overland
This itinerary describes the overland route from Cairo, Egypt to Nairobi, Kenya by public transport. This is more or less the only surface route from North Africa to East Africa accessible to Westerners, and so most overland travelers from Europe or Asia towards Southern Africa will have to pass this way (travel down the West coast of Africa is also possible, but much more difficult). The route passes through Egypt, (North) Sudan, Ethiopia and Kenya.
Almost all countries in this region prefer visas to be paid for in US dollars, and accept other currencies at unfavourable rates if at all.
Egypt: Visas are available to almost all Westerners on arrival for USD 25. This is true even if you arrive by ferry at Aswan, though in this case getting the visa on arrival may cause some delays. Some embassies (e.g. Khartoum) issue advance Egyptian visas in around 24 hours, while other (e.g. Addis) take weeks for some nationalities.
Sudan: Most westerners can in principle get a Sudanese visa in a couple days in Cairo for USD 100, though this requires a "letter of introduction" (or written statement that such letters do not exist) from your own embassy, and some embassies may be reluctant to issue anything of the sort. Getting a visa from the Sudanese consulate in Aswan is easier and cheaper. They don't require a letter of invitation and the cost is USD 50. The main exception is Americans, who currently cannot get a Sudanese visa in Egypt (or in most other countries) without "entry permission" from the Ministry of Foreign Affairs, which is difficult and time-consuming to obtain (though may be possible with the help of a tour operator within Sudan). Americans considering traveling overland through Sudan will therefore probably want to do so northbound, see below.
In Addis Ababa, westerners including Americans can get a Sudanese transit visa in 24 hours by showing an Egyptian visa (evidence that these can be obtained on arrival is not sufficient) or a plane ticket from Sudan to your home country. For Americans this costs USD 200, other nationalities probably less. The transit visa is valid for two weeks stay (can be extended in Khartoum) and entry within one month; entry does not have to be from the Ethiopian border, though you probably still have to exit a different way than you entered.
Once you have entered Sudan you are obliged to "register" your visa within 3 days; this is possible both at the borders and in Khartoum, costing USD 30-60 depending where you do it. It's not clear the 3 day deadline is enforced but you're unlikely to avoid it entirely as you will need it to exit the country.
Ethiopia: Currently Ethiopian visas are only available at Addis Ababa airport or in your home country. If you're already on the road you may have to DHL your passport home and get someone to send it to the Ethiopian embassy there for you. Your embassy may issue multiple entry visas for little more than the cost of single entries. In New York visas are issued in 24 hours for USD 70.
Kenya: Kenyan visas are available on arrival. Three-day transit visas are USD 20 but you probably want a USD 50 tourist visa. If you cross from Kenya to Tanzania or Uganda and then cross back to Kenya you don't need a new tourist visa.
Cairo-Aswan (1 day)
Air-conditioned trains link Cairo to Aswan, both during the day and overnight, taking about 12 hours. Fares are EGP 55 for second class, EGP 165 for first class, and USD 60 for a sleeper. Even second class is quite comfortable. Trains do sell out so it's worth booking in advance if you can. There are supposed to be some restrictions on which trains foreigners can take; if the train you want is subject to these you won't be able to buy a ticket from the ticket offices in Cairo or Aswan, but they will usually tell you to just buy a ticket from the conductor on the train. This only costs a few pounds more but means you don't have a reserved seat so may end up playing musical chairs. It may therefore be worthwhile to get an Egyptian (or agency) to buy your ticket for you if you want one of these trains. There are also buses between Cairo (Turgoman Garage) and Aswan (just in front of the train station), taking about the same time as the train and costing around EGP 80.
Alternatively, there are boats along the Nile, considerably slower than trains/buses and more expensive, but more scenic. These range from fairly luxurious large riverboats to the traditional Egyptian felucca which is a fairly small boat.
Aswan-Wadi Halfa (2 days)
A ferry leaves Aswan every Monday around noon, arriving in Wadi Halfa, Sudan the next morning. Tickets can be purchased in Cairo (from a window in Ramses train station) or Aswan. You will need a Sudanese visa before you can buy a ferry ticket. The ferry dock is just beyond the High Dam; there are occasional local trains, or shared taxis cost EGP 10 or less. First class passengers pay around EGP 500 and share cabins with beds, while second class passengers pay EGP 323 and have padded bench seats. Most second class passengers lay out sleeping bags/mats on deck to sleep (the best place is directly under the lifeboats as this is the only spot with consistent shade); this leaves enough of the second class seats vacant that you can probably sleep across several of these if you want. In the opposite direction, the ferry leaves Wadi Halfa every Wednesday around 16:00, arriving Aswan the next morning. Fares in this direction are somewhat lower, SDG 96 for second class or SDG 195 for first. In either direction you should probably get to the ferry port a good three hours before the scheduled departure time to deal with formalities and get a decent seat. The ferry has at least some sort of air conditioning or reasonable ventilation, such that the seating areas are bearable (though not exactly cool) even in summer.
Wadi Halfa-Khartoum (1 day)
You will most likely have to spend a night in Wadi Halfa, taking a bus to Khartoum the day after the ferry arrives or in the other direction traveling up to Wadi Halfa the day before it departs. There are comfortable, modern, air-conditioned buses making the trip in 10-12 hours and costing around SDG 85. In Khartoum the buses arrive and depart from the Sajana bus station around 2km south of the city centre. In either direction the buses depart very early in the morning, 4:00-5:00.
Khartoum-Gondar (1 day)
Buses from Khartoum to Gedaref (al Qadirif) leave from the Mina Bary bus station about 7km south of the city centre. You will then need a taxi across Gedaref to read the minibus station and catch a minibus to the border at Gallabat. After crossing to the Ethiopian side of the border at Metema, there are minibuses available to Gondar; you may end up changing vehicles at Shihedi. In either direction it is important to get an early start (departing 6:00 or sooner) to make it through in one day; in particular in the northbound direction note that the last Gedaref-Khartoum bus departs around 15:00. The minibuses involved leave when full.
Recommended stops/detours: Gondar
Gondar-Addis Ababa (1 day)
Most buses will take two days from Gondar to Addis Ababa, but your accommodation can most likely help you arrange a minibus that does it in one; you may also find such vehicles by going early to the Gondar bus station or Addis' Merkato bus station. This costs about ETB 300; slower buses will be cheaper. You're very likely to want to detour to see Lalibela and probably Axum before proceeding on to Addis.
Addis Ababa-Moyale (2 days)
Southbound buses leave from Addis' Autobus Tera (which is a metro station on the blue line) Kality bus station (which is quite far south of town). A bus to the Kenyan border at Moyale will cost around ETB 300 and stop overnight somewhere, probably Dilla. Awasa is a more pleasant and touristy place to stop but it can be difficult to get from there to Moyale in a day; opinions vary on whether it's better to get a very early minibus to Dilla and other buses from there or backtrack slightly to Shashamene and get a direct bus there. You might also have to change or get stuck in Hagere Maryam or Yebello.
Moyale-Nairobi (1 day)
The Moyale border opens at 8:00, and the bus south to Nairobi nominally leaves at 9:00, though it may wait until almost 11:00, arriving Nairobi 7:00 the following morning. You therefore have a chance of catching it even if you didn't quite get to Moyale the night before, and indeed if the stars all align you could conceivably make it from Addis to Nairobi in two days and two nights (spending a night in Hagere Maryam or Yebello). The bus costs KES 2500 and is a lot more comfortable than Ethiopian buses (about the level of US Greyhound, though without AC). The road, however, makes up for this; though recently improved it is still a very bumpy unpaved road from Moyale to somewhat south of Laisamis. You reach pavement about 12 hours after departure. The bus arrives in the Eastleigh area of Nairobi.
Frequent and cheap trains, buses and minibuses link Alexandria with Cairo in 2-3 hours. Unfortunately, the Visemar Line ferry between Alexandria and Venice is currently suspended, so there is no sea transport between Europe and Egypt, barring occasional cruises or maybe expensive freigther bookings. Buses run between Israel and Cairo, though this is something of a dead end because of the issues with Israeli passport stamps (which will lead to being denied entry to Sudan, Syria, Lebanon and some other countries). If you need/want to avoid Israel, there is a high speed ferry between Nuweiba in Egypt and Aqaba in Jordan; using this you can potentially make it between Amman and Cairo in one day (though stopping in Sinai is almost certainly worthwhile, as is detouring to Petra). Ordinarily one can travel between Jordan and Europe through Syria and Turkey, but the current political situation in Syria is unpredictable which may make visas difficult to obtain and travel unreliable or unsafe.
The quickest route onward from Nairobi to Cape Town is probably by crossing directly into Tanzania and then proceeding through Zambia and Zimbabwe to Johannesburg and on to Cape Town. Detours via Uganda/Rwanda/Burundi, Malawi/Mozambique, Botswana/Namibia, or some combination of these are all relatively straightforward.
As of mid-2011, the British Foreign & Commonwealth Office  and US State Department  do not advise against travel to any of the areas, though they do advise that such travel is not without risks.
The political situation in Egypt remains unpredictable but has been peaceful since the early 2011 revolution. Western and Southern Sudan are currently subject to armed conflict but this has not recently impacted Khartoum or other northern areas. Areas of Ethiopia bordering Eritrea and Somalia are unsafe but the route described passes far from these. Northern Kenya has had issues with lawlessness and armed banditry in the past, but the situation has improved in recent years and vehicles are no longer required to travel in convoy.
Mugging/violent crime is a risk in all of these areas, especially Nairobi, and you will generally want to avoid walking alone at night or carrying large quantities of money. Scams abound; don't trust "friendly" strangers who will greet you on the street.
Most travelers will want to take malaria prophylaxis before, during and after their visit to this region; if you choose not to, you should at least sleep under mosquito nets whenever possible, especially in more rural areas and at lower altitudes. In general none of these countries has potable tap water.