Linkable URLs for facets

I don't think this will be possible at all, and certainly not in a clean way.
First off, Drupal has a limit on path segments, which would at the very least disallow you creating a path alias at least for more than one filter (depending on the size of the base path), if not the whole thing (don't know about that, the menu system is pretty aweful).
Secondly, using the path for things like that is just wrong — if more people would do this, the entire system would break. It might break even now since the normal menu handler would have no idea that the facet suffix wasn't part of the normal URL, which could lead to unintended results for some paths.
Also, there might be searches (e.g., inside blocks) which have nothing to do with the page they are displayed on — changing the path for filtering them would be a weird thing to do, and might also break other stuff.

I agree that the results don't look nice and have certain disadvantages, but I still think this is the best way to do it. Feel free to come back with other suggestions or arguments for your case, but otherwise I'd suggest proposing a patch for the alias module to allow considering GET parameters, or to write your own module that is able to do this.

Of course this is possible in general, but as said, the Search API is designed to be very generic and flexible, and this use case is just too specific to be supported out-of-the-box. Again, you are free to write your own module to do this, which shouldn't be too hard.

You can also easily use TIDs instead of term names. And once #1012878: Add a way to index an entity directly is fixed, this will even be possible with the term names being displayed but the TID used for the link.

If you just want a general way to (automatically) create path prefixes for paths with query parameters, this really has nothing to do with the Search API, so the presentation won't hold any hints there. You could also build a facet-specific solution, practically an addition to, or fork of, the Search API facets module, but I think that would be more work and not really have any larger benefits.

So, as a starting point, you should probably just take the Path module from core.
You'll probably don't want to explicitly save all aliases, though, but just use a set transformation rule to alter all URLs for facet filters. This will reduce code immensely.
First, implement <a href="http://api.drupal.org/api/drupal/modules--system--system.api.php/function/hook_url_outbound_alter/7">hook_url_outbound_alter()</a>. There, you have to figure out whether you deal with a facet filter link and, if you do, transform it into some form that seems more useful to you (e.g., encode the filter parameters into $path). The filter arrays passed as query parameters will always be in a fixed schema, so there you shouldn't have to worry about creating a well parsable representation too much.
Since <a href="http://api.drupal.org/api/drupal/modules--system--system.api.php/function/hook_url_inbound_alter/7">hook_url_inbound_alter()</a> doesn't take care of query parameters, this apparently can't be used to transform back the path into its original form — therefore, you'll probably have to do it in hook_init() or something, setting the $_GET values manually.

Depending on whether you need this for a single site or several different ones, this might be a bit harder to do (because you need to take care of several use cases and several forms of base paths), and in the end it will always be specific to a subset of use cases (at least I think so) — but it should on the whole work smoothly for you, I guess.

Have you gotten particularly far with this miiioooo?
I'm interested in doing something similar.

Wow, miiimooo, you rock :D
I was kinda expecting a couple of code snippets or something but this is just awesome.

This weekend I'm gonna be doing a lot of testing of Search API and I will definitely make a point of trying your module!

Thanks for your contribution, great work!
I now linked to your project on the Search API project page, I can imagine this being helpful to many users of the Search API. I haven't tried your module out, yet, but will do so when I have time and give you additional feedback.

Since this is now a separate module, I think we should continue this in your own issue queue.

General feedback: The basic functionality works now, although there is still a rather major bug: #1098380: Several warnings and notices.
Also one thing you should fix is that you did something weird to Git, of which I don't even know how it could be done: you managed to create and push a 7.x-1.3 release tag, without pushing to master. So, when I checked out your module's code, I had the old 1.2 version and was kinda confused.
And of course, the user interface should be improved, Ideally, this would describe in great detail how this configuration page works. is no adequate documentation. ;) But of course you know that.

Maybe I'll contribute some more patches in the near future. Your module could be pretty important for site builders that have SEO in mind.

Dont work with search api solr =/