What table to put my foreign key in?
I'm gonna lose the theory for a minute and remind you that you're lacking a table. Bands don't have labels; record(ing)s do. A band can, throughout its career, publish recordings on many labels. 

If, when Metallica left Megaforce to sign with Elektra, you simply changed the value in the 'label' foreign key column, you'd have no record (no pun intended) of the fact that they were ever with Megaforce. Actually, the albums Ride The Lightning and Kill 'Em All are what should be associated with the label Megaforce, while Master Of Puppets is associated with Elektra. 

BandID: 
  pk in tblBand
  fk in tblAlbum

LabelID: 
  pk in tblLabel
  fk in tblAlbum