The story
Jonathon Green suggests that it means to drown out the band, that is, talk or sing louder than the band. See also beat the band.
Etymology from Wiktionary, CC BY-SA 4.0.
to beat the band
Today it means: In such a way as to surpass all competition; hence, contextually, very vigorously, at a frantic pace, to a high degree. Full definition →