The respective technical specifications are unfortunately too complicated to follow for a layman. Purportedly "explanatory" articles elsewhere gloss too much over the important points leaving me quite unsatisfied. I have fortunately come across two articles recently that seem to strike the perfect balance between these extremes.
"The Audiofile: Understanding MP3 Compression" was published in Ars Technica some time back and very nicely explains the compression algorithm behind MP3 as well as shedding some light over some of the apparent idiosyncrasies of this format. "Image Compression: Seeing What's Not There" was published by the American Mathematical Society and does a similar service for JPEG, including its successor JPEG 2000. (Come to think of it, these articles are "lossy" marvels in their own right.)
Now let us see if I can find an article with a similar depth that explains the MPEG video formats.