First, install MPG123, a super simple command-line media player:

aptitude install mpg123

Then fire the following (or save it as a script):

find /path/to/your/mp3/files/ -name '*.mp3' | mpg123 -Z -@ -

Find will pull a list of mp3 files in the specified folder, randomize them, and push them in to mpg123. Control-C will skip tracks and Control-Z will kill.

Props to Daniel Howard for first posting this here