I've been looking into this and wanted to provide you with an update. There is not a way to do a label search; however, if you search for something that is in a label, the results look like the one below, where the labels section is called out:
I'll look into seeing if there is a way to surface the entire list of labels, just like you can with tags. I'll update here when I find an answer to that, it could be a few days before I get back to you, though.
(ISC)² Online Community Manager