Here is slightly more clarification on the quote's origin. Mark Twain used it in his autobiography but attributed it to Benjamin Disraeli. The strange thing is, there is no record of Disraeli actually using it in his speeches or writings.
kisses says that the two may have spoken to each other but IMHO that's not too likely. Did Samuel Clemens ever travel to England or Disraeli travel to America? I don't know.
What's more likely is that Mark Twain lied to give weight to his point. please don't hurt me, Mark Twain was great but he became a little weird later in life.
Certain nodes here, Watergate, and Richard M. Nixon show people hate politicians and Mark Twain was definitely a populist. I guess that having Abraham Lincoln in the same era as him cut down on the possibility of attributing the quote to American politicians since no one else had the same stature.
Okay, my last two paragraphs were simply conjecture but the fact remains, Mark Twain attributed a quote to Benjamin Disraeli. If you have an alternate theory (probably "He heard it from some guy") I would like to hear it, my theory sounds vindictive.
edited later As additional support you can go to this website http://www1c.btwebworld.com/quote-unquote/p0000149.htm. Sorry about the Internet link but I don't want to rip off the website wholesale.