How to encode a WAV to a mp3 on a Android device
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/
As far as i know you can't do this using only the tools in the SDK. According to the official developer guide there isn't an MP3 encoder in the platform (Android Supported Media Formats), so you have to port an encoder on your own using the NDK, then write some wrapper code to receive the audio samples through JNI.
I'm currently working on porting some audio decoders from the Rockbox project for my own music player, and it can record audio into MP3, so maybe you should try to look into it's source and find the encoder library. Most of the decoders have ARM optimalizations which speeds up things noticable, so i guess some of the encoders have also this addition.