works without anything:
needs a soundbank
available through additional libs:
I suggest starting with low quality wav files (11khz, 8bit, mono). I also recommand to use the same editor for cutting and saving the wavs. That way you avoid several problems and well it's always a good idea to trimm em down.
If you have lots of sounds ogg would be a good option (lib overhead is about 80kb).
Tracker formats like mod and xm are nice for music.
Mp3 isn't a free format - just don't use it (use ogg instead - it's better anyways).
Midi and rmf (beatnik) needs a soundbank, which is available in 3 sizes (ranging from 0.3 to 5mb)... so you can forget that option. Rmf is pretty cool, but you won't find any free music in that format nor a free editor (there is only one which costs about $400). [Btw the SDK comes with a soundbank wheras the JRE doesn't]