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". This makes it easy to enter a phrase and hit the search mail button.
Searching Gmail, just like Google, can be very simple or very sophisticated.