Tandem-running is a recruitment behavior in ants that has been described as a form of teaching, where spatial information possessed by a leader is conveyed to following nestmates. Within Temnothorax ants, tandem-running is used within a variety of contexts, from foraging and nest relocation to – in the case of slavemaking species – slave raiding. Here, we elucidate the transcriptomic basis of scouting, tandem-leading, and tandem-following behavior across two species with divergent lifestyles: the slavemaking Temnothorax americanus and its primary, non-parasitic host T. longispinosus. Analysis of gene expression data from brains revealed that only a small number of unique differentially-expressed genes are responsible for scouting and tandem-running. Comparison of orthologous genes between T. americanus and T. longispinosus suggests that tandem-running is characterized by species-specific patterns of gene usage. However, within both species, tandem-leaders showed gene expression patterns median to those of scouts and tandem-followers, which was expected, as leaders can be recruited from either of the other two behavioral states. Most importantly, a number of differentially-expressed behavioral genes were found, with functions relating to learning and memory formation in other social and non-social insects. This includes a number of up-regulated receptor genes such as a glutamate and dopamine receptor, as well as serine/threonine protein phosphatases and kinases. Learning and memory genes were specifically up-regulated within scouts and tandem-followers, not only reinforcing previous behavioral studies into how Temnothorax navigate novel environments and share information, but also providing insight into the molecular underpinnings of teaching and learning within social insects.