Android - Where (and how) does Android store music playlists?

They're stored in your music.db file - mine is /data/data/com.google.android.music/databases; I'm not sure if this is exactly the same across all devices but I'd guess it probably is.

They live in a combination of the LISTS and LISTITEMS tables, which are defined as such:

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>

Interestingly, if you're using the new Google Music Beta, playlists that you create don't seem to appear in other apps but they do have entries in the DB. It looks like this is possibly because the MusicSourceAccount field is set to your Google Music account id; other apps set it to 0, and those appear across all apps that take data from the DB.