freie Formate sind Formate, die frei (kostenlos) für jeden nutzbar sind. Es steht keine Firma dahinter, die Lizenzgebühren verlangt. Zu diesen Formaten gehören zum Beispiel Ogg Vorbis. MP3 ist unter Linux auch kein Problem, wobei es sich dabei nicht vollständig um ein freies Format handelt. Laut Wikipedia sind "Kernbereiche von MP3 durch Patente geschützt".
IIRC laufen die MP3-Kernpatente bald aus. (2007/2008) Bisdahin wird wohl das EPLA noch nicht in Kraft sein, das sie möglicherweise in Deutschland durchsetzbar machen würde.
Für Videodaten ist glaube ich MPEG-4 ein freies Format (wobei ich das nicht beschwören könnte).
MPEG-4-Kerntechnologien sind patentiert, auch hier gilt, in Deutschland nicht durchsetzbar. Trotzdem gibt es freie (XviD, ffmpeg) und proprietäre (DivX) Implementierungen.
Da die Firmen, denen die proprietären Formate gehören, Lizenzgebühren verlangen, kann man die entsprechenden Codecs nicht mit kostenlosen Betriebssystemen wie zB Linux vertreiben.
DivX erlaubt den kostenlosen Download einer vereinfachten Version seines Codecs, aber trotzdem erlauben sie Novell nicht die Verbreitung auf der Suse-DVD. Es ist also durchaus denkbar, dass proprietäre Codecs ohne rechtliche Bedenken genutzt werden können.