This question is primarily about URL design and only incidentally about rewriting. Once you've designed your URLs to be cool, there are lots of ways to make them work including rewriting at the server level or using a web framework that does URL-based dispatch (I think most modern web frameworks do this these days).
Beauty is in the eye of the beholder, but I do agree with you that a lot of search urls are ugly. What makes them so? I think the primary thing that makes URLs ugly is cruft in the URL that doesn't add semantic meaning but is the result of an implementation detail, like (.aspx) or other extensions. My rule is that if a URL returns (X)HTML than it shouldn't have an extension, otherwise it ought to.
In the case of a search, the fact is that the standard search syntax does add meaning: it indicates that the page is a search, it indicates that the arguments are named and reorderable. The ugliness primarily comes from the ?&= characters, but really anything else you do will be to replace these same characters with more attractive characters like |-/, but at the cost of making the URL opaque to any software that wishes to parse it like a spider, a caching proxy server, or something else.
So think carefully about not using the standard syntax and be sure you have a good reason for doing it. I think in the case where your arguments have a natural order and must all be defined for the search to make sense and are compact, you could push it into the URL. For example, in a blog URL you might have:
/weblog/entries/2008
/weblog/entries/2008/11
/weblog/entries/2008/11/22
For a search defining the entries from 2008, nov 2008, and 22th of november 2008, respectively. Your URLs should be unique and unambiguous; sometimes people put in /-/ for missing search parameters, which I think is pretty compact. However, I would avoid pushing potentially long parameters, like a free-form text query, into the the URL.
/weblog/entries/containing/here%20is%20some%20freeform%20text%20blah%20blah is not any more attractive that using the query syntax.
If you are going to use the standard query syntax, then picking argument names that are meaningful might improve the attractiveness, somewhat. products/search?description="blah", though longer, is probably better than products/search?q="blah". At this point it's diminishing returns, I think.