¿Dónde (y cómo) guarda Android las listas de reproducción de música?

Se almacenan en tu archivo music.db - el mío es /data/data/com.google.android.music/databases; no estoy seguro si esto es exactamente igual en todos los dispositivos pero supongo que probablemente lo sea.

Residen en una combinación de las tablas LISTS y LISTITEMS, las cuales están definidas de la siguiente manera:

sqlite> .schema lists
.schema lists
CREATE TABLE LISTS(Id INTEGER PRIMARY KEY AUTOINCREMENT, Name TEXT NOT NULL, 
    SourceAccount INTEGER, SourceId TEXT, _sync_version TEXT, 
    _sync_dirty INTEGER NOT NULL DEFAULT 0, MediaStoreId INTEGER, 
    ListType INTEGER NOT NULL DEFAULT 0, ListArtworkLocation TEXT);
CREATE INDEX LIST_SYNC_INDEX on LISTS(SourceAccount,SourceId);
sqlite>

sqlite> .schema listitems
.schema listitems
CREATE TABLE LISTITEMS(Id INTEGER PRIMARY KEY AUTOINCREMENT, 
    ListId INTEGER NOT NULL REFERENCES LISTS, MusicSourceAccount INTEGER NOT NULL,  
    MusicSourceId TEXT NOT NULL, ClientPosition INTEGER NOT NULL, 
    ServerPosition INTEGER NOT NULL DEFAULT 0, SourceAccount INTEGER, SourceId TEXT,
    _sync_version TEXT, _sync_dirty INTEGER NOT NULL DEFAULT 0, 
    ServerOrder TEXT DEFAULT '', ClientId TEXT);
CREATE INDEX LISTITEMS_ORDER_INDEX ON LISTITEMS (ListId, ServerOrder, ClientPosition);
CREATE INDEX LISTITEMS_SYNC_INDEX on LISTITEMS(SourceAccount,SourceId);
sqlite>

Curiosamente, si estás usando el nuevo Google Music Beta, las listas de reproducción que crees no parecen aparecer en otras aplicaciones pero sí tienen entradas en la base de datos. Parece ser que esto posiblemente se deba a que el campo MusicSourceAccount está configurado con tu id de cuenta de Google Music; otras aplicaciones lo configuran como 0, y esas aparecen en todas las aplicaciones que toman datos de la base de datos.