You're positive you haven't entered your info anywhere? At all? That'd be my first guess. Second, CC theifs don't always strike right away -- they could've had your credit card logged weeks or even months ago and just didn't make it down the "list" far enough until recently.
Get yourself a month-long credit report from
www.Equifax.com and make sure the rest of your information wasn't leaked as well. If it was stolen they may have your other cards or even enough information to apply for a loan, etc.