Updated: There is a blog today about updated Gmail search modifiers that allow you to do this with a simple search!
has:nouserlabels
Note: Because of Gmails threading you will have labels on some of the messages in the derived list because some messages in a thread will have labeling while some won't.
Original answer:
The Gmail advanced search help page says:
label:Search for messages by label*There isn't a search operator for unlabeled messages
Example:
from:amy label:friends
Meaning: Messages from Amy that have the label "friends"Example:
from:david label:my-family
Meaning: Messages from David that have the label "My Family"
