As I have just switched over to using GMail exclusively, and a question came up on how you can search based on multiple search criteria.
Here is a link on Google detailing the different search syntax. For example, if you wanted to search for emails labeled “Registrations” and starred, simply the following into the search box in GMail:
If you have more than one label you want to search for, enter a separate label:
label:registration label:another-label is:starred