I know that are many MP3 encoder libraries, but any of them could work on a PIC microcontroller?
I doubt it, even if you are using a dsPIC.
If you are targeting a chip that constrained you probably want to look at codecs designed to operate in a small embedded environment rather than MP3. If you just want to do compressed audio the Speex library is a possible solution. There is a version packaged by Microchip for the dsPIC processors.
Depending on what you are actually trying to do, something like μ-law or A-law might be sufficient.
If you are making a device that supports MP3 encoding, also consider the MP3 patent issues.