Caveat - I'm not a lawyer
You either have to:
A) Find royalty free music that is labelled as OK to use in a professional setting. That's generally not hard to do.
B) Create your own.
C) Get permission from the creator of the music.
There's a lot of royalty free music out there, and quite a bit of it is labelled as fine for commercial use. Again, not a lawyer, but I think if it's labelled royalty free with no further clarification, you're fine to use it in a performance. If it's restricted from using in a commercial setting, it usually says so.
Create your own - That's on you. I "play" a couple instruments but I am by no means a musician - the instruments I have any skill with are the kinds you don't have to know anything about music theory to be able to play. Some day I'll get the equipment to record it properly but until then, I just do the other two options. The only thing you may have to worry about here is if the song you create ends up sounding too close to another song, AND the person finds out you're using it, you could be in trouble (Vanilla Ice, anyone?)
Getting permission can be surprisingly easy depending on who owns the rights. I tend to listen to a lot of smaller artists who are not signed to major labels, something that is easier and easier to find these days as folks realize they can make a good living managing their own music online. You also find folks who make music because they enjoy making music and then put it up and are happy with whatever income happens to appear. Message them and ask what it would take to use their music for a magic performance (Or ongoing magic performances, as the case may be) - many of them will say it's fine as long as you buy the album. Just recently I got in touch with a guy in England who does this amazing, creepy, sampled music using old phonographs and he gave me permission to use his stuff as long as it's in private shows and not big corporate stuff or TV.
NOTE: The "get in touch with them for performance rights" thing also applies to tricks that otherwise restrict performance rights.