Future Mars missions will involve aerial and surface robotics. Previous studies have examined the possibility of using a single robotic balloon in the Martian atmosphere to obtain meteorological and topological data. It may be advantageous, however, to use a combination of aerobots along with surface rovers to map and study Mars. This combined system will be much more effective if the different elements are working in tandem to gather complementary information. The aim of this thesis is to investigate cooperative strategies for exploring a given piece of Martian terrain using a system comprising several different elements. Various aerobot concepts and rovers are reviewed, the capabilities of different types of aerobots and rovers were compared, and a trade-off was made to select a preferred system. Collaboration strategies developed between aerobots and rovers enable them to navigate and explore the target terrain with greater precision and reduced intervention from mission control on Earth. An airship + tethered depot + nanorovers architecture resulted as the best resolution. A suite of instruments were configured to gather useful information. It is concluded that heterogeneous robotics with a complementary suite of instruments work in concert will greatly increase the mission value.