If you've read How CDs Work, then you know about how to store sound digitally. In a digital answering machine, these same principles are used to convert a caller's message into a stream of bytes. A microcontroller digitizes the caller's voice using an analog-to-digital converter and stores it in low-power RAM (random-access memory).
So let's say a caller leaves a 15-second message. That might translate into 30,000 bytes of digitized data. These bytes are stored at a specific address in RAM (see the How C Programming Works for a discussion on memory addresses). To play the message back, the microcontroller reads the 30,000 bytes from RAM and plays them through a digital-to-analog converter.
RAM is a high-speed memory device, so the microcontroller can erase one of the messages and easily move the other messages forward into the freed-up space.
Here are some interesting links: