I was going to say the same thing. Such a hardy species I would think would be the product of an incredible amount of evolutionary progress. How do they fit in with the rest of the living species taxonomy?

Don't get too excited - the Wikipedia article (very good) explores their genome and taxonomy. Fossilised records hard to come by but cambrian and Cretaceous records have been found. So probably boringly terrestrial

Or it could simply mean that they came to Earth a long time ago.

Sure, but as of now, there is no positive indication they are extraterrestrial. They fit into the species cladogram, they don't seem to suddenly appear as a time anomaly, they just seem like extremely tough little guys.

I read somewhere that they can absorb DNA from foreign sources (other animals, etc) into their cells when they rehydrate, leading to an accelerated rate of evolution.

Here's an article about that: http://phys.org/news/2015-11-huge-chunk-tardigrade-genome-fo...

Doesn't really solve the problem of how life first arose. It just pushed the whole thing back into space.

But pushing it into space does open up some interesting possibilities. There must be some very exotic chemistry during and after a supernova, or when a comet has an unusually close encounter with a star.