REST is about resources. What resource will your query return? A set of data? How is that set identified? How is it parameterized? This should determine the URL you would use with the GET operation:
GET /customers would retrieve all customers
GET /customers?q=<query> would retrieve all customers matching the query
EDIT: The following not quite so clear to me
Thinking about the query as being about retrieving a resource which is a set of customers (for instance), I started to wonder about well-defined subsets of the set of all customers. Consider things like:
GET /customers/state/MA Retrieve all customers in Massachusetts
GET /customers/country/UK All in the UK
GET /customers/country/UK/postalcode/001-234 All in that postal code in the UK
Resources like these make sense to me as clearly identified resources, and not as queries. I'd continue to use a query string to retrieve an arbitrary set of customers, but where there is a natural partition of customers, I might indicate that in the URL space.
Recall that the GET operation is meant for idempotent operations, and is meant to promote caching. The response to these queries should permit some reasonable amount of caching (one day, perhaps). This would permit a client machine or proxy server to cache the result set for a period of time, saving server round trips.