[Crito]

Airships would be harder to make work on Mars, but once you have it working you would almost certainly be in a better position.

Also, Wolfram Alpha peggs the air pressure at 39km on earth, the height Felix Baumgartner jumped from, as 330 Pa. It has the atmospheric pressure on Mars (presumably the average at the surface) as 650 Pa. So balloons that will float in that, at least at a low altitude, are not beyond our engineering grasp. (and unmanned balloons on earth have gone down to as few as 55 Pa http://en.wikipedia.org/wiki/High-altitude_balloon).