You can search many applications on iPhone, including Mail, Calendar, iPod, Notes, and Contacts. You can search an individual application, or search all the applications at once using Spotlight.

From the main page of the Home screen, flick left to right.
If you’re on the main Home screen page, you can press the Home button to go to Spotlight. From the Spotlight page, press the Home button to return to the main Home screen page. You can also set iPhone to go to Spotlight when you double-click the Home button. See Home.
On the Spotlight page, enter text in the Search field. Search results appear automatically as you type. Tap Search to dismiss the keyboard and see more of the results.
Icons to the left of the search results let you know which application the results are from. Tap an item in the results list to open it.
Contacts—First, last, and company names
Mail—To, From, and Subject fields of all accounts (the text of messages isn’t searched)
Calendar—Event titles, invitees, and locations (notes aren’t searched)
iPod—Music (names of songs, artists, and albums) and the titles of podcasts, video, and audiobooks
Notes—Text of notes
Spotlight also searches the names of the native and installed applications on iPhone, so if you have a lot of applications you may want to use Spotlight as a way to locate and open applications.
Enter the application name, then tap to open the application directly from the search results.
Use the Search Results settings to choose which applications are searched and the order in which they’re searched. See Home.