I think query parameters are okay as well.
Search and filtered sets kinda push the boundaries of what it is useful to make RESTful. (For search, what's the "resource"? What would it mean to DELETE or POST to the resource?)
There isn't sensible RESTful version of every API; if what you want to do is not really based around "resources" (in the HTTP sense), then there's no point making it RESTful. I don't think it's possible to make a reasonable RESTful interface to a chess server, for example. (The only way to do it is to tunnel a non-RESTful API.)