During the development of multicellular organisms, cells become different from one another by changing their genetic program in response to transient stimuli. Long after the stimulus is gone, “cellular memory” mechanisms enable cells to remember their chosen fate over many cell divisions. The Polycomb and Trithorax groups of proteins, respectively, work to maintain repressed or active transcription states of developmentally important genes through many rounds of cell division. Here we review current ideas on the protein and DNA components of this transcriptional memory system and how they interact dynamically with each other to orchestrate cellular memory for several hundred genes.