Blargkaboom points out that in one of the demo screenshots during the iPhone SDK event showed off a new search icon in the Contacts application.
This search icon is not available on the current version of the iPhone firmware. At present, users can only slide their finger down the alphabet to scroll quickly through their contact list, and can not search for specific names.
Hopefully the next iPhone revision will bring us this search functionality. iPhone 2.0 is scheduled for release in late June.