Merriam-Webster's Dictionary of English Usage has a section on this.
Some usage books and schoolbooks view the phrase up and with the same distaste they direct at take and, go and, and try and (which see). Up and is no bucolic idiom redolent of our frontier past, however; it is current on both sides of the Atlantic, and is used in general publication, often by writers of more than ordinary sophistication. It, too, is not highly formal.
They then give four examples, the oldest of which is 1968, and in all of which up appears to be inflected like an ordinary verb. (e.g., suddenly upped and won).
The way I use it, and the way that I see it used in many of the older citations in Google Books, up and is not inflected. For example, from Mark Twain (1884)
The doctor he up and says "Would you know the boy if you was to see him again, Hines?"
This is a very old construction: "he up and told the gentleman" appears in a 1687 translation of Don Quixote, while the oldest inflected example I could find in Google Books is he upped and he tould them, which appeared in 1845 in Dublin.
I suspect that the uninflected usage is the original, and that over the years the construction up and verb gradually became regularized. This would point to the origin being elision in some construction "(verb) up and do something", although I haven't been able to find any discussion of the etymology.