How to make a DIY 'Tickle Me Elmo' style plush toy?

Hi,

I'm looking for advice on how to build a 'Tickle Me Elmo' style plush toy, as I am a bit of a newbie. 

The concept is that there will be three spots on the plush monster with pressure sensors (or buttons?), namely on his head, belly and nose. 
Each of these should have their own set of sounds, about 3 to 5 variations (depending on memory) each. 
My aim is that if you press for example the nose, one of the 5 programmed sounds will play. 

So basically I need to be able to:
* Record up to 15 different sounds, grouped in three categories, and connect them to the appropriate sensor. 
* Play one of 5 random sounds in the appropriate category when the sensor is activated 

I would prefer if this was 'portable', so I can hide all of the electronics, parts and battery in the plush monster. Is this possible and how big should my power source be? 

So, I'm hoping you guys can suggest some electronics, microcontroller and parts for me. Then I can start experimenting!

Thank you in advance for your feedback,
Lims

Look for Arduino Making things talk. It will show you how to use an Arduino with a Wave shield so when you hit a button an MP3 is played from an SD card.