I thought the phrasing the birds and the bees might have been a corruption of the birds and the beasts, as in the children's song Animal Fair and in various Biblical references, but birds and bees appears often enough in the Corpus of Historical American English to suggest that the alliterative phrasing was not uncommon to evoke a vernal or bucolic scene, as in the birds and the bees, the flowers and the trees, or blossoms, birds, and bees. It seems birds and bees have often been paired.
According to The Phrase Finder, the connection between birds, bees, and human mating may date to Samuel Taylor Coleridge's 1825 poem Work WIthout Hope, but the connection is rather tenuous, the same for John Burroughs' 1875 series of essays for children about nature, Birds and Bees, Sharp Eyes, and Other Papers. American songwriter Cole Porter's 1928 hit Let's Do It, Let's Fall in Love (Ella Fitzgerald cover) is also suggested. The original lyrics being too lengthy for radio play, various trimmed versions have been produced, but the signature line is
Birds do it, bees do it
Even educated fleas do it
Let's do it, let's fall in love
The Google NGram is not convincing that this was a touchstone, but it is an unreliable gauge for something that might have been considered taboo subject matter for quality publications, or might have appeared in the spoken vernacular but not found its way into print until much later.
In the specific sense not just of sexual reproduction, but of imparting its purpose and mechanics to children, COHA turns up a line narrated by a boy in Heroes by Ben Norris, published in Harper's in 1933, that may be suggestive. As I do not have access to the full text, however, that could simply be my own projection:
Some doctor had given a lecture with illustrations about the birds and bees, only Oscar said skunks and snakes were more appropriate.
The meaning is more explicit in Walk in the Sun (1944) by Harry Brown:
"The birds and the bees. Didn't your old man ever tell you about the birds and the bees?"
"Naw."
"You hear that, Friedman? Judson never heard of the birds and the bees."
Friedman was on firm ground now. "Terrible," he said. "Shall we tell him?" "Maybe we better." Rivera held out his hand. "Give us a butt, Judson, and we'll tell you all about the birds and the bees."
"I ain't got a butt," Judson said sadly.
But the first time I could find it in a quality news source is in the January 13, 1945 issue of The Billboard, in a review of the musical Central Park (which opened on Broadway as Up in Central Park):
Contrasting the villan role of Noah Beery Sr., as Boss Tweed, are the comedy antics of Betty Bruce. She milks her meager lines and situations with mugging niceties and gets her big vocal moment with a delightful comedy song, The Birds and the Bees, which gives lyrical levity to sex education.
So while the origin is uncertain, probably related to biological discussions of flower pollination and of birds mating for life and building a nest together before laying their eggs, it seems to have broken into polite conversation in the 1940s, and may have been understood as slang or a euphemism for several decades prior.