When you go into Gmail > Settings > Labs you’ll see a new feature has been added (well maybe you won’t see it because of the ever-growing number of Labs features, bu tits there)… its called Search Autocomplete. Gmail Lab’s Search Autocomplete acts exactly as it sounds. As you type in the Search Mail text box you will see suggestions.

Check out their post for more information.

MORE GMAIL STUFF
New in Labs: Gmail search made easier (and lazier)
Gmail Advanced Search Operators