Download LameLib:

Due to the license on MP3 technology, the encoder must be downloaded separately. The LameLib files for Macintosh are at spaghetticode.

Direct download link: LameLib-Carbon.sit
This is a StuffIt archive. It should automatically uncompress.

Behold the LameLib:

You should see something that looks like this:
library.png
called LameLib.

The best place to put this file is in the Audacity application folder. If you have trouble doing this, just move LameLib to your home directory.

Tell Audacity where LameLib is:

Open Audacity. Open a sound file — any file will do. Go to File: Export MP3

Agree to the various questions, until you are asked where LameLib is