I'm pretty sure the answer is no for Visa/MC and basically no for Amex, and it's actually illegal in some states, but what if they just rephrase it as "We're giving you a discount if you choose to pay cash!"...
This isn't so much a legal issue, the prohibition on giving discounts was written into the merchant agreements that most of the major credit card companies enforced on businesses that accepted their credit cards.
That is, until the recent Financial Reform Bill (2010) passed Congress. It changes everything. (The logic on this is a little convoluted, so read carefully)
Credit card companies can no longer prohibit merchants from requiring a minimum purchase amount to use a credit card. Meaning: That if merchants want to, they can now stop taking credit cards for a $4 latte.
Credit card companies can no longer prohibit merchants from giving discounts for cash.
Here is an article with a lot more detail: Financial Reform Bill Good News for Credit Card Holders
Here is a link to the actual bill details and content: HR 4173 - Dodd-Frank Wall Street Reform and Consumer Protection Act
Here is the relevant part:
(A) IN GENERAL.—
A payment card network shall not, directly or
through any agent, processor, or licensed member
of the network, by contract, requirement,
condition, penalty, or otherwise, inhibit the
(i) of any person to set a minimum dollar
value for the acceptance by that person of
credit cards, to the extent that —
(I) such minimum dollar value does not
differentiate between issuers or
between payment card networks; and
(II) such minimum dollar value does not
exceed $10.00; or
(ii) of any Federal agency or institution of
higher education to set a maximum dollar
value for the acceptance by that Federal
agency or institution of higher education
of credit cards, to the extent that such
maximum dollar value does not differentiate
between issuers or between payment card
(B) INCREASE IN MINIMUM DOLLAR AMOUNT.—
The Board may, by regulation prescribed pursuant
to section 553 of title 5, United States Code,
increase the amount of the dollar value listed in
This subsection is supposed to take affect "at the end of the 12-month period beginning on the date of the enactment of the Consumer Financial Protection Act of 2010." In other words, July 21st, 2011.
I'm not sure about the laws in specific states. However it's part of their merchant agreement that they can not charge a fee for a customer paying with credit card. It's also against merchant agreements to require a minimum purchase to use a credit card, although this is less commonly enforced.
Apparently (http://fso.cpasitesolutions.com/premium/le/06_le_ic/fg/fg-merchants.html) merchants can offer a cash discount.
Offering payment by credit card, though practically a requirement in todays retail environment, is a privilege for the merchant. It's a way of making buying convenient for the customer. As a result, penalizing the customer in any way is not just against their agreement, but rather disingenuous as well.
edit: here's a bit more information about what they can and can't do. Amex prohibits discrimination, so if a merchant can't do something to a Visa/MC customer they can't do it to an Amex customer either. http://fso.cpasitesolutions.com/premium/le/06_le_ic/fg/fg-merchants.html