If you need to model client-side application state it's best to have one source of the state. This is the one of the problems client side javascript MV(V)C frameworks attempt to solve. I'm mostly familiar with backbone.js and ember.js so I can speak to those.

Backbone.js

Create a model called Playlist and a collection called Playlists. Add a property to your Playlists collection currentPlaylist that holds the current playlist. Then define a view called PlaylistView and define a render method on it. Wire up event triggers and bindings such that when currentPlaylist changes, the playlist is automatically re-rendered. This would require moving your template rendering to the client, but you'll probably want to do that anyway to reduce server roundtrips and reduce the load on the server caused by rendering.

Ember.js

Create a controller (similar to backbone collection) with a property called currentPlaylist and populate the controller with all of the playlists represented as Ember.objects. Then in a playlist handlebars template included on the page you can bind to playlists.currentPlaylist and the template will re-render automatically when playlists.currentPlaylist changes.

I'm obviously leaving out the vast majority of the details, but those are best left the the framework documentation, examples and tutorials.

disclaimer: I'm new to client-side frameworks which is part of the reason I left out most of the details. I appreciate anyone who can correct me if I'm in error.

A mix of session and local storage would be a good approach.

But instead of fetching the whole playlist just fetch the X (for example 10) next tracks and maybe also the X previous ones. Once the player gets to the last song, it fetches the next 10 songs, the previous ones can be calculated in the client.

The data model could be just a hash where element [0] is the current song, elements [X] are the next songs and [-X] the previous ones.

Storing the playlist information client-side seems reasonable to me, but you can also use the session to reference the current song and playlist, so when a user comes back or really reloads your site you still get the song without doing a database call.

I would suggest c) In Session.
Session data can be accessed with relative ease on both client and server side.

Filling your Redis cache with specific user data doesn't scale up particularly well.

LocalStorage - correct, this will fail for a large % of users at current date.

CustomData Attributes - just plain messy, as noted.

Just my 2 cents.