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