Covalent modification of DNA via deposition of a methyl group at the 5' position on cytosine residues alters the chemical groups available for interaction in the major groove of DNA. The information content inherent in this modification alters the affinity and the specificity of DNA binding; some proteins favor interaction with methylated DNA, and others disfavor it. Molecular recognition of cytosine methylation by proteins often initiates sequential regulatory events which impact gene expression and chromatin structure. The known methyl-DNA-binding proteins have unique domains responsible for DNA methylation recognition: (1) the methyl-CpG-binding domain (MBD), (2) the C2H2 zinc finger domain, and (3) the SET- and RING finger-associated (SRA) domain. Structural analyses have revealed that each domain has a characteristic methylated DNA-binding pattern, and this difference in the recognition mechanism renders the DNA methylation mark able to transmit complicated biological information. Recent genetic and genomic studies have revealed novel functions of methyl-DNA-binding proteins. These emerging data have also provided glimpses into how methyl-DNA-binding proteins possess unique features and, presumably, functions. In this review, we summarize structural and biochemical analyses elucidating the mechanism for recognition of DNA methylation and correlate this information with emerging genomic and functional data.