Legumes are highly important food, feed and biofuel crops. With few exceptions, they can enter into an intricate symbiotic relationship with specific soil bacteria called rhizobia. This interaction results in the formation of a new root organ called the nodule in which the rhizobia convert atmospheric nitrogen gas into forms of nitrogen that are useable by the plant. The plant tightly controls the number of nodules it forms, via a complex root-to-shoot-to-root signaling loop called autoregulation of nodulation (AON). This regulatory process involves peptide hormones, receptor kinases and small metabolites. Using modern genetic and genomic techniques, many of the components required for nodule formation and AON have now been isolated. This review addresses these recent findings, presents detailed models of the nodulation and AON processes, and identifies gaps in our understanding of these process that have yet to be fully explained.