¿Dónde se almacenan y manipulan estos datos de la cola de canciones actuales?

El truco aquí es que grooveshark, soundcloud, etc. son aplicaciones cliente de JavaScript de una sola página, que no vuelven a cargar la página. Lo que le permite escuchar su lista de reproducción mientras navega por otras secciones de la aplicación.

Los datos para la cola se pueden almacenar en almacenamiento local / cookies o directamente en la vista. En el caso de grooveshark, parece ser que los datos de la canción se almacenan en la vista directamente.

  

El atributo rel debe ser la ID de la canción que debe reproducirse.

Almacenamiento: como mencionaron Hadar Weiss y Quora User, la respuesta a la pregunta uno es: DOM.

Manipulación: jQuery es una buena biblioteca para manipular elementos DOM ya que se encarga del cumplimiento cruzado del navegador, es liviano y te ayuda a escribir código limpio.

Complementos
Si desea utilizar los complementos de jQuery con HTML5, puede probar este enlace:
http://www.codebasehero.com/2011

Bjoern tiene razón. Solo usa el DOM.
En los navegadores modernos, puede mantener miles de registros y manipularlos sin la interversión del servidor, y todo funcionará de maravilla. Si insiste en un esquema de varias páginas, puede usar API de almacenamiento local como IndexDB. También le permitirá restaurar “sesiones” de cola antiguas para los usuarios que regresan.