Waiting for the moment to grab an iPod shuffle by myself, I came across this article.
A pretty look inside an iPod shuffle, a Mac OSX-oriented dissection on how music files and playlist are stored and available as seen from a mounted volume on a Mac and browsed via Terminal.
Still to be written: how to change the XML file, maybe through a simple text editor, that iTunes and the iPod shuffle itself uses as a reference and playlist for the stored audio files.
Applematters.com blog, by the way, is run by Hadley Stern, the author of O'Reilly's iPod and iTunes hacks.
Check this link for free chapters too.