Learning has been studied extensively in the context of isolated individuals. However, many organisms are social and consequently make decisions both individually and as part of a collective. Reaching consensus necessarily means that a single option is chosen by the group, even when there are dissenting opinions. This decision-making process decouples the otherwise direct relationship between animals' preferences and their experiences (the outcomes of decisions). Instead, because an individual's learned preferences influence what others experience, and therefore learn about, collective decisions couple the learning processes between social organisms. This introduces a new, and previously unexplored, dynamical relationship between preference, action, experience and learning. Here we model collective learning within animal groups that make consensus decisions. We reveal how learning as part of a collective results in behavior that is fundamentally different from that learned in isolation, allowing grouping organisms to spontaneously (and indirectly) detect correlations between group members' observations of environmental cues, adjust strategy as a function of changing group size (even if that group size is not known to the individual), and achieve a decision accuracy that is very close to that which is provably optimal, regardless of environmental contingencies. Because these properties make minimal cognitive demands on individuals, collective learning, and the capabilities it affords, may be widespread among group-living organisms. Our work emphasizes the importance and need for theoretical and experimental work that considers the mechanism and consequences of learning in a social context.