searching emails in s3
On my Samsung Galaxy s3 I can hold down the menu button inside the built in mail app - This enables the search function.

You can search for


All
Title
Sender
Date
Attachment
Advanced (which is a combination of Title+Sender+Date)