In its simplest form, all an .m3u playlist needs to be is a list of filenames, so it can be created by redirecting or piping a simple directory listing.
Thus Windoze users can easily create an updated list of their whole mp3 collection, or all the mp3s in a directory and subdirectories as a playlist (for shuffle play), presumably) and start playing it using a DOS batch file like this (change drive and path to suit, obviously):
@echo off
c:
cd \My Music
dir /b /s *.mp3 > everything.m3u
start everything.m3u
Note that Winamp retains the shuffle setting between sessions, but will always start with the first file in the playlist, so if you want not to start with the same tune every time, create a dummy mp3 file somewhere that will come up first on the list (call it _.mp3 in your starting directory, for example). Winamp also doesn't like filenames in .m3us that included accented characters, unfortunately. Unfortunately, filenames containing high-ascii characters get scrambled as dir output uses OEM rather than ANSI characters, so you need a filter if this is an issue. Such a thing can be found (inter alia, I'm sure) at http://utenti.lycos.it/papero/free/qota.zip - put it somewhere in your PATH and then change the fourth line to:
dir /b /s *.mp3|qota /a > everything.m3u
You'd think that a shell script to do the same thing under Linux etc. would be equally trivial, but ls by itself won't actually produce a plain list of fully qualified filenames with a certain pattern while recursing through subdirectories so you have to use find instead:
cd ~/mp3s #(or wherever)
find -name *.mp3|xmms -p
Thanks to spiregrain for suggesting find when I couldn't make ls do it (it never displays filepaths). Of course, I haven't actually tested this one - let me know if it works or not. And if you've found any way of controlling the shuffle command of any common MP3 players from the command line. ...