The first use is from 1865 but how did the first people to hear it know what it meant? What does it mean? I know what it indicates but not how it was derived.
dictionary.com suggests that it is a direct translation from German:
It probably originated as a direct translation of the German Und wie! [1920s]
Of course, that just pushes the problem back a step…
What is the origin of the phrase “And how”?
“and how! Indicating ‘intensive emphasis of what someone else has just said,’ ‘and how!’ is a long-popular catchphrase first recorded in 1924. The Americanism possibly derives from the German ‘und wie!’ or the Italian ‘e come!’, meaning the same thing, and once very common among Americans of German and Italian extraction, respectively.” From Encyclopedia of Word and Phrase Origins by Robert Hendrickson (Facts on File, New York, 1997).
Here’s the 1865 usage from Bayard Taylor (in a letter printed in an 1884 book):
B. Taylor letter 16 June in Taylor Life and Letters Bayard Taylor (1884) II xviii 434: I finished an article for the ‘Atlantic’ that day. As if I were not ‘a tool of the elements!’ ‘And how?’ as the Germans say (Americanicé — ‘You’d better believe it!’) [OED].
I found other pre-1924 usages.
Atlantic magazine, February 1879.
We saw less of Bayard Taylor than we had hoped during the winter, for he was away from home most of the time lecturing. When spring came he determined to remove to New York. We must live together, he said; as he was more prosperous than I he would pay the rent of the house. It would be so jolly to have a library in which we could write. And how we would write!
C. Deveureux Venus in India I 109: ‘I’ve had, I dare say, many more men than you’ve had women!’ Frank and how!