Does a musical band or similar service under an LLC have to file for a foreign qualification in every state they play a show in/employ their service?
Being a musician isn't that different from other businesses in this respect. A company has to register or qualify in a state if it is "doing business" in the state.
Whether a company is doing business in a state is a very blurry line. If you have an office or employees working in a state then you are definitely doing business, but occasional visits to a state for business reasons would generally not rise to doing business. See this article for more details.
If you go on tour to a bunch of states, then I expect you are not doing business in those states and don't need to qualify. If you have a weekly gig in another state that is close to your home, then you probably are doing business there and should qualify.
If you are somewhere in between and are not sure, then you can probably get away with not qualifying, especially if your revenue is small. It is not uncommon for small companies to neglect to register in other states, and it is hard for states to enforce this especially since the "doing business" requirements are very vague.