There is currently a parameter in the API that allows you to filter search results by label (see http://docs.atlassian.com/atlassian-confluence/REST/latest/#id288504) but queries that use it return an empty results list.

eg:

/rest/prototype/1/search/site?spaceKey=TST&type=page&label=testing

will return nothing.

Workaround for Confluence 3.5:

User a query parameter with 'labelText' to define the label:

/rest/prototype/1/search/site?spaceKey=TST&type=page&query=labelText:testing

This workaround no longer works in Confluence 4.0+