How did the phrase "butterflies in stomach" originate or what is the story behind this phrase?
Under the definition ‘A fanciful name (usually plural) used of the fluttering sensations felt before any formidable venture, especially in . . . butterflies in the stomach’, the Oxford English Dictionary provides this as its earliest recorded use, in 1908, of the expression:
The three o'clock train going down the valley . . . gave him a sad feeling, as if he had a butterfly in his stomach.
The plural form doesn’t occur until 1944:
There was no electrical response to the movement of that firmly gentle hand, no butterflies on the backbone.
Only in 1955 does the expression as we know it today appear:
With butterflies in her stomach . . . she ascended the pretentious flight of dirty marble steps.
Etymology Online dates butterflies in the sense of "light stomach spasms caused by anxiety" to 1908.
As for why, I believe it's just a descriptive phrase meant to capture the fluttering sensation you feel when nervous, as if butterflies were rapidly flapping their wings in your stomach.
Why we blame butterflies and not, say, hummingbirds or bees, I can't say, though it might have to do with their perceived delicacy and harmlessness.
As Barry answered, the OED gives 1944 for first plural use and 1955 for the current meaning. I've found an antedating of the plural with our present day meaning from 1943.
The February 1943 Boys' Life has an account from a paratrooper and former scout, Bill Gardner, on his very first training jump:
I landed all right and although I'll always have butterflies in my stomach every time I go up, I'll never experience the fear of that jump. Somehow I feel as though I've accomplished something worth while.