Searching mail is the greatest benefit of Gmail! Using Google's search interface, it's quick and easy to find messages.
Take a peek at the two buttons to the left of the entry bar: There's a button to "Search Mail" and a button to "Search the Web." This makes it easy to enter a phrase and hit the search mail button. Then if nothing's found in your mail history, hit the search the web button and, well, search the web for the phrase.
Searching Gmail, just like Google, can be very simple or very sophisticated.
The "Search the Web" button has been removed. There is a petition at http://www.petitiononline.com/gmail001/ to bring it back.