Diagnosaurus allows you to browse by symptom, disease, organ system, or view all of the 1000+ differential diagnoses. There are versions of this tool for the iPhone/iPod Touch, as well as PDA's.
iPhone app is $0.99 from the App Store on iTunes. The PDA version is a free download.
If you'd like more advice on finding medical apps for mobile devices, please visit this site.