Mapping and navigation have gone hand-in-hand since long before robots existed. For almost as long, maps have also been a key form of communication, allowing someone who has never been to an area to nonetheless navigate that area successfully. In the context of multi-robot systems, the maps and information that flow between robots are what enables effective collaboration, whether those robots are operating simultaneously or years apart in time. In this thesis, we argue that maps must go beyond encoding purely geometric or color information in order to enable increasingly complex autonomy, particularly between robots. We propose systems for mapping and localization, showing that semantic maps can be an important end in themselves as well as a means to achieve improved global localization in a variety of contexts. We then build on these ideas and employ semantic maps to underly a framework for multi-robot autonomy, focusing in particular on air and ground robots. A distinguishing characteristic of this thesis is that we strongly emphasize field experiments and testing, and we demonstrate that these ideas can work at scale in the real world. We also perform extensive simulation experiments to validate our ideas at even larger scales. These experiments and systems constitute a step forward in large-scale, collaborative multi-robot systems operating with real communication, navigation, and perception constraints.