.m3u

Just take a copy of your WinAmp playlist and send them that!

But how is the file laid out?

#EXTM3U
This is just a header to the file. I think the #EXT means it's not a filename
#EXTINF:423,Baz Luhrmann - (Everybody's Free) To Wear Sunscreen
E:\music\Baz Luhrmann - Sunscreen.mp3
Here's a file where the track has been indexed. WinAmp has extracted the name from the ID3 tag, and the '423' means that there are 423 seconds (or 7 minutes, 3 seconds) in the song
E:\music\Lemon Jelly - Lemon Jelly - Kneel before your god.mp3
This one hasn't been indexed. Just the plain filename.
Pink Floyd - Another Brick In The Wall Pt 2.mp3
This one isn't in the E:\music\ directory, but in the local directory #EXTINF:240,Wayriders - Hazy
E:\music\Wayriders - The Moose -9 - Wayriders Promo - Hazy.mp3
And the file just ends there. No tailers, that's it.

And your friend now knows what songs you have, don't have, if they're full versions, and other cool foo.

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. ...