How can I use HATEOAS and Query Parameters for RESTful search?

Using the syntax described in the current draft of the URI template spec you would do:

/users{?surname,maxresults}