To survive in changing environments, animals need to learn to associate specific sensory stimuli with positive or negative valence. How do they form stimulus-specific memories to distinguish between positively/negatively associated stimuli and other irrelevant stimuli? Solving this task is one of the functions of the mushroom body, the associative memory center in insect brains. Here we summarize recent work on sensory encoding and memory in the Drosophila mushroom body, highlighting general principles such as pattern separation, sparse coding, noise and variability, coincidence detection, and spatially localized neuromodulation, and placing the mushroom body in comparative perspective with mammalian memory systems.