The first thing to do when you lose your passport in Kenya is to make a photocopy of the picture page and your current visa before you lose the passport. It is best to keep a paper copy with you, another paper copy somewhere in the US where somebody can fax it to you, and a third copy on your computer with a label that helps you find it (e.g., "Passport.jpg").
If you want to be extra safe, make similar arrangements with your driver's license and birth certificate (NB: also important if you hope to become President). None of this will spare you any hassle, but it might save you money, because the greedy US Government will bill you by the minute for all time spent verifying your identity so that it can pay for its extravagant wars and give away free abortions and BMWs to welfare mothers.
The very next thing you should do when you lose your passport is look for it. The obvious places to start are the places where you normally keep your passport. These might be zippered pockets of your luggage, shelves in your room, or drawers in your office (NB: does not apply to people without offices). If you are a lady, check the underwear drawer: ladies often keep their passports amongst their unmentionables, which means the passport is safe from people who do laundry, but vulnerable to perverts. If you do not find your passport in the places where you normally keep it, then it is probably somewhere else.
One temptation is to keep searching the same places over and over again, in the hopes that you will find your passport on the eleventh try. This only works if your passport has been stolen by somebody very conscientious who returns it to precisely the same place he/she took it from. Stop it! You are wasting precious time that could be spent waiting in line at the Embassy.
Other places to look include places where your passport might have landed accidentally if you were careless with it. The most convenient place to start is between the seats of your vehicle, ideally as it is being driven (by somebody else) to Nairobi so that you can search the rest of the places where the passport might have landed, which is a bounded two-dimensional area ("polygon") with vertices at Jomo Kenyatta International Airport, Wilson Airport, the Country Lodge Hotel, Westgate Shopping Centre, Nyayo House, and the Moi Avenue Matatu Station. If you have searched this area carefully and still not found your passport, then try calling Joseph Kariuki. He might have it in his house.
Should all of these approaches fail, then your passport is Gone. Perhaps you lost it because you are an absentminded academic, or perhaps it was stolen to be sold on the black market to Somali terrorists. The distinction is immaterial: either way, the passport will end up in the hands of Somali terrorists, and your carelessness has put American lives at risk. Asshole.
Go to the nearest police station and report it lost/stolen, and make sure you receive a stamped abstract from the police records. This is important; to be on the safe side, you might ask them to stamp it twice, so that it looks extra-official. If possible, do this in whatever small town you are in, because the police station in your small town, while depressing, is less depressing (and has shorter lines) than any police station in Nairobi.
After you have obtained your police report, visit nairobi.usembassy.gov, look under the "Citizen Services" tab, and download form DS-11. Fill it out. Then obtain four 2x2 inch photographs of your ugly, terrorist-enabling head. If you are wondering where to find a 2x2 inch passport photo in a country that has largely discarded inches, ounces, and other oppressive imperial units, proceed to "PhotoMural," a photography store in Warwick Centre, which is conveniently located next to the US Embassy and is used to dealing with assholes like you. Bring 500 shillings. If you also want a matted photograph of a flock of flamingos standing in the shape of the African continent (minus South Africa and most of Namibia, Botswana, and Zimbabwe), then bring 1500 shillings. If you want a photograph of a flock of flamingos standing in the shape of an etiolated duckling with its feet stapled together, then take your custom elsewhere. PhotoMural doesn't have that one.
Once you have your police report, passport photos, and completed DS-11 form, you may proceed to the US Embassy, which is easily recognizable as a bomb shelter opposite the UN Headquarters in Gigiri. Hopefully you have already made an appointment. In practice, this hardly matters, since everyone who arrives is forced to take a number, and the digital counter on the wall is stuck at #548. But if you have an appointment, you will feel less guilty about elbowing your way to the first open window.
Whether or not you have an appointment, do not bother showing up after 3:00 pm (noon on Fridays), or on the weekends. US Embassy personnel are very busy attending important dinners and parties with their Nairobi expat friends, and you're just going to have to wait. Call your airline to reschedule your flight for the night of your date with the Embassy. Before you do this, fly at least 100,000 miles on that airline during the previous calendar year so that they treat you with a minimal level of basic human decency.
When you go to the Embassy, bring a credit card and something to read while you wait. There is a separate entrance for assholes who have lost their passports, which is between Warwick Centre and the main Embassy. Approach the gate with your hands up and your documents between your teeth, repeating the following phrase: "US citizen, stolen passport." This can be difficult to say with your documents between your teeth, but important if you want to avoid being shot. Consider practicing with a piece of scrap paper during your ride or flight to Nairobi. You will be forced to surrender your bag, computer, and anything else with an on-off switch, including mobile phones, two-way pagers, and other approved electronic devices, which is why you should bring a book.
Once inside, be aggressive with all of the other passport and visa seekers, but very polite to anybody with a badge or a position behind a window. You might be on US soil, but you are still very much in Kenya. Don't waste time pondering that paradox; space is relative -- just deal. Behave in the way you have learned to behave in these situations.
If you follow these instructions, you have a chance of obtaining a new temporary passport within three hours of arrival at the Embassy. Keep your police report, as well as all the papers that they give you at the Embassy, as you will need them to leave the country. You will have surrendered two of your new passport photos; send the other two in with your application for a new passport when you return to the US. Good luck.