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 ability— (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 networks. (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 subparagraph (A)(i)(II).
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