Extracting audio from MP4 video into MP3

Use ffmpeg:

ffmpeg -i input_file.mp4 -vn -b:a 128k -c:a libmp3lame output_file.mp3

(Don't forget to adjust the audio bitrate, -b:a, otherwise you might get a huge file even for a low quality source.)

Many digital players actually support AAC audio as well, so you can try extracting the original AAC audio stream, without having to reduce quality even more:

ffmpeg -i input_file.mp4 -vn -c:a copy output_file.m4a

For older versions of ffmpeg, you'll need to use -ab & -acodec options instead of -b:a & -c:a.

Most MP4 videos use AAC audio, and most player devices can play AAC audio, normally in an M4A (differently-named MP4) container. Re-encoding to MP3, especially with a low bitrate input (most internet video), can lead to noticeable loss, even on low-end headphones. I would recommend using avconv/ffmpeg on the command-line

avconv -i input.mp4 -vn -c:a copy output.m4a

or

ffmpeg -i input.mp4 -vn -c:a copy output.m4a

To convert every MP4 in a directory:

for f in *.mp4; do avconv -i "$f" -vn -c:a copy "${f/mp4/m4a}"; done

Some players (like my cheapy cheapo mobile phone) can play AAC audio, but not in an M4A container, and for that you have to use

avconv -i input.mp4 -vn -c:a copy output.aac

Now, some older devices genuinely can't play anything but MP3, and for those you can either use grawity's solution, or

avconv -i input.mp4 -vn -c:a libmp3lame -q:a 2 output.mp3

This will create a variable bit rate (VBR) MP3 which, apart from specialised needs like streaming, should be preferred. -q:a 2 will get you an average (over a number of files) bit rate of around 190 kbit/s; for more information on encoding VBR MP3s, see here.