I know that are many MP3 encoder libraries, but any of them could work on a PIC microcontroller?
There are special MP3 decoding chips available, so it seems that using or porting software for this isn't needed. Have a look at this page, for example, and this even is an outdated page from 2001.
I believe that you need a 32-bit processor for this. No way to do mp3 encoding/decoding with PIC16 or PIC18. Here is a link for a project using am ARM7TDMI processor (a quite modest 32-bit processor). It uses the Helix library.
What pic microcontroller? They range from 8-bit PIC10's to 40MIPS+ 16-bit dspic33F's. The latter (30F, 33F) might be able to do it, if their DSP functions somehow align with the encoding algorithm. Some of the "ADC" type of these controllers seem aimed at audio processing (but that might be simple sampling and transformation too, not directly encoding). They can also do the sampling entirely in hardware (ADC stores it to mem using DMA)
If you think doing it using the CPU, forget it, it takes something in the magnitude of a 300-500MHz PC chip to do this realtime, and probably even 100-200MHz 32-bitters won't hack it.
Decoding is a lot cheaper and can be done by a 486. Less even if you cut stereo etc.
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.
The Speex library is what I use. It is easy to use but you do need at least a 32 bit processor. Hope this helped.
I know this is not PIC, but...
AVR32 has new "UC3A3" members that are intended for MP3 playback. I'd at least have a look at that platform, first. They should be able to give reference designs.
Why PIC?
Addendum: AVR32 is rather powerful, and it gives utterly good kick-per-watt. I wouldn't see any problem using it for MP3 encoding (recording) as well.
This Atmel Application Note seems to mention MP3 encoding. "The MP3 decoder source code is provided under GPL style license."
Here and here are some comments that may be relevant reading.