Recording voice on an arduino is going to take up a lot of memory but with the wave shield you can store your voices onto an SD card. The shield will also let you plug in some headphones/speakers. Attach a mic and your on your way.
Bluetooth Modules: This guide should get you started http://www.instructables.com/id/Voice-Activated-Arduino-Bluetooth-Android/
The negative about this is that you need a cell phone that has bluetooth capabilities (android, iphone, etc) and you would be talking to your phone instead of through your mic (you wouldn't need to purchase the mic in this case).
Last option, easyVR: EasyVR 3 Plus Shield for Arduino - COM-15453 - SparkFun Electronics
I just found this item, i don't know much about it unfortunately. But from the description it looks like you can use this for audio output and input (so you won't need the adafruit wave shield I first linked at all). Again, I don't know much about this product..