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.