Cellular phenotypes can be ascribed to different patterns of gene expression. Epigenetic mechanisms control the generation of different phenotypes from the same genotype. Thus differentiation is basically a process driven by changes in gene activity during development, often in response to transient factors or environmental stimuli. To keep the specific characteristics of cell types, tissue-specific gene expression patterns must be transmitted stably from one cell to the daughter cells, also in the absence of the early-acting determination factors. This heritability of patterns of active and inactive genes is enabled by epigenetic mechanisms that create a layer of information on top of the DNA sequence that ensures mitotic and sometimes also meiotic transmission of expression patterns. The proteins of the Polycomb and Trithorax group comprise such a cellular memory mechanism that preserves gene expression patterns through many rounds of cell division. This review provides an overview of the genetics and molecular biology of these maintenance proteins, concentrating mainly on mechanisms of Polycomb group-mediated repression.