How does lame get round the software patent issues described in the
64Studio faq?
Basically, software patents aren't valid in all countries (I'm not sure what the rule is here, but if you're concerned about such things it's worth looking into). The developers of LAME leave it up to the end user to get a license if they so choose to do so, and only distribute the encoder in source format.
Now, having said that, you can usually find precompiled binaries in a lot of different repositories, though rarely in official distribution ones. If you can't find a debian repository that has it, you can just compile the upstream package. I just had a quick look, and on Ubuntu, it's in the multiverse repository.
Ah, more reading has led me to the package called 'toolame'. Apparently it's a drop in replacement for lame, but it encodes in layer 2 (instead of 3) to avoid the patent issues. That may or may not help, but there it is.
