**Updated:**
There is a [blog today][1] about updated Gmail search modifiers. There is now a way to do this with a simple search!

    has:nouserlabels


**Original answer:**

The Gmail [advanced search][2] 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"

Sorry!


  [1]: http://gmailblog.blogspot.co.uk/2012/11/search-for-emails-by-size-and-more-in.html
  [2]: http://mail.google.com/support/bin/answer.py?answer=7190