We investigate the evolution of memory usage in environments where information about past experience is required for optimal decision making. For this study, we use digital organisms, which are self-replicating computer programs that are subject to mutations and natural selection. We place the digital organisms in a range of experimental environments: simple ones where environmental cues indicate that a specific action should be taken (e.g., turn left to find food) as well as slightly more complex ones where cues refer to prior experience (e.g., repeat the action indicated by the previous cue). We demonstrate that flexible behaviors evolve in each of these environments, often leading to clever survival strategies. Additionally, memory usage evolves only when it provides a significant advantage and organisms will often employ surprisingly successful strategies that do not use memory. However, the most powerful strategies we found all made effective use of memory.