I've just done this route, and it was awesome!

Here are some recommendations:

Get your passport and carnet stamped out in Nairobi, this is the only place to do it legally.
Drive 200kms on good tar to Nanyuki.
Here in Nanyuki is your last chance for a decent supermarket (Nakumatt). I advise you fill up all your fuel tanks here.
Head NW out of town past the Nanyuki River Camp.
9km out of town take the right fork in the road towards Kinamba.
Kiss the tar, you won't see it again for more than 1000km!
This road is locally known as the "Stock Road". Those with high vehicles beware of the Elephant Gates - they are steel cables strung across the road with steel cables hanging down. They are to prevent elephants getting into farms etc. Drive through at pace and you'll smash your windscreen!
At the time of writing this was a great gravel road all the way to Kinamba.
Head north from Kinamba towards Maralal.
We spent the night in the yard of some Kenyan Settler's farmhouse at Mugie. Ask nicely! They are super friendly people, but we did make sure we provided the s! N0 42 36.2 E36 35 33.1
From Kinamba the road is badly rutted and corrugated.
You can get fuel from a fuel station in Maralal, but you're starting to get remote now so supplies aren't guaranteed.
We bushcamped on a deserted farm in beautiful surroundings. N1 34 16.0 E36 43 12.6
Next town north is Baragoi. This is the last chance to fill up from a fuel station for the next 700kms. Expensive fuel of questionable quality may be found on the black market elsewhere.
Head north through South Horr and on to Loiyangalani on the shores of Lake Turkana. We camped at the excellent Palm Shade Campsite.
Head north out of Loiyangalani. Just before Gusi Village turn left onto a track through the desert (N3 03 44.3 E36 47 55.2)
We bushcamped under an Acacia Tree in the desert - a fantastic spot! N3 11 45.0 E36 46 38.1
At N3 22 09.5 E36 45 20.2 you rejoin the main track which comes from North Horr heading for Sibiloi. Join the track heading west for Sibiloi National Park.
Cost for entry is $20 per day plus 300 shillings for a car. We have a big overland truck but told them the weight was less than 3 tonnes, which they bought. This costs 500 shillings.
Take the main track around the eastern side of Sibiloi National Park. Do not attempt to use tracks which haven't seen recent use, even if they exist on the map. You will most likely lose the track and get stuck (both of which happened to us!)
As you leave Sibiloi heading north you get to Illeret. Here you must go to the police who will take down your details. They don't have a stamp for your passport, but we were able to get them to give us a letter stating we'd left Kenya on such-and-such date etc. We got this from the Chief of Police, an amiable guy called Charles.
We spent the night at the Catholic Mission in Illeret run by a German priest.
Head north for Ethiopia. When you get to the main gravel road (N4 44 53.2 E36 10 27.5) turn left to go to Omorate where you will find immigration and customs.
You are now in the Omo Valley. I recommend going to Turmi to see the Hamer People. Try get to see a bull jumping ceremony. We camped at the Mango Campsite which is excellent.
Next I recommend going to Jinka to see the Mursi People (lip disks, body paint, etc). We stayed at the excellent Rocky Campsite. In Jinka you have the first opportunity to find diesel in a fuel station (not petrol though, that is from barrels on the black market across the road)

Overall we averaged about 15 or 20kph - the road can be very rough in sections but is extremely beautiful and well worth it. Take a LOT of water and as much fuel as you can carry. Fuel consumption will go up on the bad roads.

For photos and details of this trip check out our journal on www.overafrica.org

Hope this helps!
Cheers
Steve