While not exactly from Mars, these "space spiders" sound interesting nonetheless:

Space 'spiders', small robots able to crawl along mesh webbing, will be tested during a joint mission with the Japanese Aerospace Exploration Agency, the European Space Agency and the Vienna University of Technology. The Furoshiki satellite is scheduled to launch on January 18, 2006. To save on mission costs, the rocket carrying the satellite will have a sub-orbital trajectory; only about ten minutes of microgravity will be available before the satellite begins its descent.

The plan is to develop these little machines for use in very big space construction projects.