Pure Java
Look into Tritonus’s clean room implementation of javasound which offers an MP3 encoder plugin here: http://www.tritonus.org/plugins.html
Secondly, I would suggest looking into jzoom’s libraries JLayer or JLayerME: http://www.javazoom.net/javalayer/javalayer.html (this may only be decode, not sure)
If those doesn’t suit your need you can look at this article from 2000 about adding MP3 capabilities to J2SE (with source): http://www.javaworld.com/javaworld/jw-11-2000/jw-1103-mp3.html
Native route
If you want “native” performance I would look at an FFmpeg or Lame port for Android.
Lame: http://lame.sourceforge.net/