There are many great ways to handle this problem. It is a recommendation problem, not a classification problem, as pointed out by others. There are many ways to do recommendation with a data set like this. I'll point out a few methods and you can choose one or try them all.
The first method is called user-based collaborative filtering. The basic idea is to give users recommendations based on the tastes of like-minded users. So, you'd be trying to recommend music based on the listening history of users who have listened to the same songs. Such data can be modeled as a graph or sparse matrix. Then, you choose the exact algorithm depending on how you want to model your data.
The second method is called item-based collaborative filtering. Rather than associating users together, this strategy looks at the set of items a user has 'rated' (the songs a user has listened to) and calculates how similar they are to a specific target item (song), or even to all the songs in your data set. It grabs the set of most-similar items and uses various methods to predict how much a user will like the song.
In this case, you only have binary data (user listened to it or they did not). These calculations tend to work best with actual rating scores (like a 5 star system) because this gives more detailed variation amongst items in the data set.
The third option is to model your data in a graph database like Neo4J and write graph traversal queries in order to find similar items. If you like graph theory, this can be a lot of fun. The sky is the limit in regards to what kinds of traversals will return good results. To get started, think of the users and songs as nodes in the graph, and 'listened' as the edge. $user->listened->$song
Because of ratings and item-based filtering, and because there are probably many songs in your data set, and each user only listens to a very small portion of them, I'd first try a user-based collaborative filtering method which uses sparse matrix operations to calculate recommendations. If your data set is large, these computations scale horizontally so you can leverage parallel processing if you run into performance issues.
You can find more detail about collaborative filtering in this paper: http://files.grouplens.org/papers/www10_sarwar.pdf