It is a story, set mostly on earth, or in near-earth orbit, of a band called Nova who get contracted to play a gig on "The Underworld", a prison colony orbiting the earth, which is going to be their ticket to fame and fortune. The Magician is the leader of the band, very interested in old-fashioned music, and slightly psychic. The Queen of Hearts is their 'cuber', cubes being a fancy new sort of drum incorporating some interesting visual effects, who is very obviously an enigma, and who subs in for their regular cuber at the last minute. The mystery of her past is unveiled as they reach the Underworld, and she is linked with the prisoner, Terra Viridian, who killed 1500 people 7 years ago for absolutely no reason.
There's a lot of psychic occurrences which give this the feel of a fantasy set in space. People acting on hunches, events converging, odd coincidences which may or may not be coincidental. But there are bits here and there that really benefit from the future tech. The instruments played by the band members are fabulous, as are the visual effects they use on stage. I don't know any other author who could possibly get you to imagine the sound and light show. The access system for the Underworld is quite futuristic and adds a lot. Radio communications is also really vital to the plot - being able to have people in physical different locations but communicating with each other in a semi-public fashion isn't something you can manage easily in a fantasy setting. So this isn't just a fantasy novel set in space, it really uses the technology, but it still manages to feel more like fantasy than SF.
A lovely story, like all of McKillip's other books it actually lets me see the world she's describing and in this particular case, hear it too.