I'm surprised by all the pro-credit answers here, debit has some definite advantages.
Most importantly, when you pay with a credit card, the merchant pays around 3% of the transaction to the credit company. In many states, they are forced to charge you the same amount, and this is frequently toted as ''consumer protection''. But consider what this means for the business: they loose money for every credit transaction, and they're legally forbidden to do anything about it. So you're taking 3% from a business and handing it over to a massive cooperation.
To make matters worse, the buisness is inevitably going to have to raise their prices (albiet by a small amount), so in the end the average consumer has gained nothing. On the other hand, the credit card company wins big, and they use their profits to pay lobbyists and lawyers to keep these rules in place. To put in the worst possible light, it's essentially legal extortion, verging on corruption.
As for the fraud protection offered, while it may be true that credit cards will offer a more hassle-free reimbursement (i.e. you just don't have to pay the bill) if your card is stolen, consumer protection laws also extend to debit: in many cases your bank is legally required to cut you a check for all the money you lost.