Cellular differentiation is one of the hallmarks of complex multicellularity, allowing individual organisms to capitalize on among-cell functional diversity. The evolution of multicellularity is a major evolutionary transition that allowed for the increase of organismal complexity in multiple lineages, a process that relies on the functional integration of cell-types within an individual. Multiple hypotheses have been proposed to explain the origins of cellular differentiation, but we lack a general understanding of what makes one cell-type distinct from others, and how such differentiation arises. Here, we describe how the use of Boolean networks (BNs) can aid in placing empirical findings into a coherent conceptual framework, and we emphasize some of the standing problems when interpreting data and model behaviors.