Adult tissues in multicellular organisms typically contain a variety of stem, progenitor and differentiated cell types arranged in a lineage hierarchy that regulates healthy tissue turnover and repair. Lineage hierarchies in disparate tissues often exhibit common features, yet the general principles regulating their architecture are not known. Here, we provide a formal framework for understanding the relationship between cell molecular ‘states’ (patterns of gene, protein expression etc. in the cell) and cell ‘types’ that uses notions from network science to decompose the structure of cell state trajectories into functional units. Using this framework we show that many widely experimentally observed features of cell lineage architectures – including the fact that a single adult stem cell type always resides at the apex of a lineage hierarchy – arise as a natural consequence of homeostasis, and indeed are the only possible way that lineage architectures can be constructed to support homeostasis in renewing tissues. Furthermore, under suitable feedback regulation, for example from the stem cell niche, we show that the property of ‘stemness’ is entirely determined by the cell environment. Thus, we argue that stem cell identities are contextual and not determined by hard-wired, cell-intrinsic, characteristics.