You’d call George W. Bush “Mr. President” to his face (although I’d be strongly tempted to call him something else). Cabinet secretaries are “Mr. [or Madame] Secretary.” I’ve heard mayors referred to as “Mr. Mayor” now and again.
But in speaking to a governor, senator or congressman (or -woman), you’d simply refer to his or her title, without the “Mr.” or “Madame” prefix.
Why the difference?
I’m guessing because there is only ONE president, but multiple governors and senators.
caveat: ONE president in office at any given time.
Yes, but former presidents are often addressed as “Mr. President.”
The form of address comes from George Washington’s preference. There was much debate as to what it should be, but Washington eventually made it known that “Mr. President” was his preference.
Note that back in the 18th century, “Mister” meant more than it does today; not every man was referred to at “Mister.”
Governors existed before the U.S presidency and there was already an established protocol: they were addressed as “Your Excellency.” There was no protocol for a national executive officer who was not already a king, prince, duke, or whatever and the usage “Mr. President” evolved to fill that role. (Several other honorifics were proposed, but discrded as sounding too much like European nobility.)
The “Your Excellency” has fallen out of use in reference to governors (and even bishops) in our purportedly classless society, but as the high muck-a-muck, the president’s honorific has hung on.
I thought bishops were “Your eminence”.
And what exactly is the right formula for the governor? Because I work right across the street from the state capitol, and the governor’s office is actually in the same building. I see her now and again, and while I haven’t been in a small-talk situation as of yet, it could easily happen one day. Oh, and how about the lieutenant governor? I’ve been in an elevator with him a few times and he’s extremely friendly; I called him “Mr. Cherry” last time, but if there’s official protocol, I’m curious what it is.
And mayors were referred to as “His Honor.”
That is for cardinals.
Here is the infoplease list of forms of address. However, they seem to be geared more toward letter writing or introducing them as speakers than actually bumping into someone on the street or yelling at them at a press conference.
Shit, that’s right.
What was I thinking trying to correct you? 
… which is not correct, but it’s done anyway. The appropriate title for an ex-president is the title he had before becoming president. So it should really be Governor Clinton, Governor Reagan, and Governor Carter, but who’s going to correct anyone when they’re addressing you as President so-and-so.
The Mayor of New York City is officially referred to as Hizzonnerthemayor.
Years ago when I did PR for New York State, “The Empire State,” I always tried to get the title of the governor changed to Emperor.
Just think of the publicity The Emperor of New York would get.
Nobody took me seriously, unfortunately. 
What did they call every man?