How do I search for contacts that do not have an email address?

You can't use Advanced Search to search for contacts with no email address. Instead, you need to use another search tool named Search Builder.

A: Go to Search –> Search Builder

Select the record type Contacts, the field Email and the operator Is Empty.