You probably got skimmed at an ATM or a card reader in a shop. I'm always paranoid about these so I prod around at the card slot before putting the card in.
Sorry this happened to you though. Your bank will definitely refund the fees. The real nuisance is waiting for a new card and then changing your details on websites and things.