You could start here: Mp3 Licensing and vorbis.com

In theory many MP3 encoder vendors should be paying license fees: in practice some do, some don't, it's not widely enforced and there are grey areas. The Debian Linux distribution does not actually include a MP3 encoder (because Debian are very purist about free software), but there is a "free software" encoder based on publicly available reference code from Fraunnhofer labs which is considered legitimate by some. Actually that's history: see LAME - it seem the whole code base has been rewritten. There might be a potential debate about whether patents are being infringed, though.

WMA stuff comes included with Windows but I don't think the specs for how it's done are freely available for 3rd party software developers.
WAV is also a Microsoft invention but it's simple and well documented and everybody uses it.

Anahata