[eluser]WanWizard[/eluser]
key => value pairs is indeed the way to go. If you process them in a foreach(), you don't have to bother with sequence as well. /user/1/sort/asc works the same as /sort/asc/user/1.
I try to store as much as possible in the session, to avoid a long URL. Don't forget that you have to do a lot of validation on the URI segments, since the user can type them in they can be anything. Only if a user should be able to bookmark something, I use the URL to pass the value.
Storing it in the session also has the advantage that the selection can be remembered. If the user navigates away from the page, and comes back later (within the same session), sort order and filter/search value are rembered and you can present the page as it was on the last visit.