***UPDATE***
After braving the wilds of the internet, I've come to a solution! You are correct in that a codec is needed to play Mp3s. This is avoided by the adafuit wave shield because it is designed to only play .wav files. The arduino can play an audio file, just not a compressed audio file. The .wav files are not compressed which is why they are so big.
So playing Mp3's off of the EEPROM is a "NO-GO" for the Arduino without a Mp3 codec to decompress it.
However, this can be done with a .wav file, and luckily the audio file I want to play (3 secs of a bird call) is only 200KB as a .wav file. So if I use a 2Mb EEPROM, like the M95M02 ( http://www.digikey.com/product-detail/en/M95M02-DRMN6TP/497-11405-1-ND/2679405 ), and a DAC, like the MAX5541, I should be able to store and play the audio file without a SD card!
This method would only be useful for very small .wav files; however, it would be perfect for a project like a holloween decoration that screams or moans when it detects motion, or maybe cool doorbell ringtone. Or perhaps a for a bird feeder that calls the birds to it for optimal bird watching action!
Here is an article I found on how to interface the M95M01 (the smaller version of the M95M02) to the arduino that is useful:
http://strayspark.wordpress.com/arduino-bit-banged-spi-eeprom/
Thanks to Crossroads and Mike for helping me through this! I will post the results of the circuit later.