You can use random() function to generate a random tune number. Read this page:http://arduino.cc/en/Reference/Random
You can use a wave shield to store a few tunes, then use random() to pick one at random to play.
The switch is easy. Connect one end of the switch to arduino ground and the other end to an arduino input say digital pin 2. Set that pin as input with internal pullup resistor. Then keep reading that input. If it becomes low then pick a tune at random and play it.
I don't have a wave shield so someone else could help you on how to stop a tune.
Sounds like a fun project.