The U.S. military origin theory
Most of the reference books I've consulted agree with Phrase Finder (cited in choster's answer) that the phrase arose in the later stages of World War II among U.S. servicemen. For example, Barbara Kipfer & Robert Chapman, Dictionary of American Slang, fourth edition (2007) has this:
for the birds adj phr Inferior; undesirable, of small worth; LOUSY : [examples omitted] {WWII armed forces; a euphemistic shortening of shit for the birds, because some birds eat animal feces, it is the equivalent of bullshit or horseshit}
And from J.E. Lighter, Random House Historical Dictionary of American Slang (1993):
for the birds to be regraded with contempt or scorn; not to be taken seriously; no good.Also (vulgar) shit for the birds. [First two cited occurrences:] 1944 [Robert] Olds, Helldriver Squadron[: The Story of Carrier Bombing Squadron 17 with Task Force 58] 98: That's something strictly for the birds. 1944 in A[merican] S[peech] XX 148: That's For The Birds. It's meaningless. ... Shit For The Birds. Nonsense, drivel, irrelevant matter.
The actual entry in American Speech (volume 20 of which appears to be dated 1945) reads like this:
SHIT FOR THE BIRDS. Nonsense, drivel, irrelevant matter. (A variant: THAT'S FOR THE BIRDS. It's meaningless.)
Lighter also cites this interesting instance:
1957 A[merican] S[peech] XXXII 240: In 1942, when I entered the U.S. Army, the disparaging term that's for the birds was in common use among officers and enlisted men. ... The metaphor alludes to birds eating droppings from horses and cattle.
If the person quoted here (fifteen years later) has his dates and language right, "for the birds" was already current in the U.S. Army in 1942. But no one has identified any print occurrences of the term, used in the relevant sense, from that year or earlier. As far as I know, Lighter's 1944 citation from Robert Olds is the earliest instance put forward in a published reference work.
The U.S. college origin theory
Another place where the expression seems to have been used fairly early on is on U.S. college campuses. The first three relevant matches that an Elephind newspaper search turns up are all from college newspapers—one from late 1943 and two from late 1944.
From A. X. L., "Reviewer Finds Combined Comic, Literary Magazine Lacks Punch of Former Editors," in the Columbia [University, New York] Spectator (November 12, 1943):
Most of the new issue, including an equestrian cover, is devoted to the football team, its past and present efforts. Nevertheless, much of the material, including said cover, is a rehash from older copies of the mag and has ripened, not improved, with age.
O[f the] more recent offerings, some are on a high level and a large portion is only fit for the birds. The usual sly, sharp quips aimed at Spectator and your reviewer in particular misf[i]re, possibly because the caustic wit of one W. W. Wager, recently fled to Harvard from the fair fields of Columbia, has either been omitted, deleted, or sidetracked. Wager does show up, however, with a brilliant poem on the 1934 Rose Bowl victory and a brief ode to Lou Little.
From Hank Johnston, "The Sport Wail," in the [Kent, Ohio] Kent Stater (December 12, 1944):
The girls of Lowry Hall are organizing a basketball team to raise funds for a new bird bath in the Atrium. "There's nothing cheep about us," the girls emphasized. When asked why they proposed to put a bird bath in the Atrium, the lovely ladies replied, "Someone told us that the Registrar's office was for the birds." This is good, clean fun.
And from "Campus Scout," in the [Urbana, Illinois] Daily Illini (December 20, 1944):
INFAMOUS FIRS[T] WORDS: "You say there'll be plenty of room on the 5:56—"
...
FAMOUS LAST WORDS: —Yep. For the Birds!"
The first instance is intriguing because—in a clearly figurative way—it uses the wording "fit for the birds." This could be a euphemistic play on "shit for the birds," or it could be an allusion not to the certain birds' eating habits but to the common practice of using newspaper to line the bottom of a birdcage, In any case, that is the earliest confirmed instance of "for the birds" that I'm aware of.
Conclusion
The U.S. Army and U.S. college campuses were closely bound during World War II, in part because a lot of patriotic college students enlisted after Pearl Harbor and in part because of the draft (which was already in place in 1940), so it is hardly surprising that "for the birds" appeared in both places early in the expression's existence.
An issue of Collier's Magazine from 1945 may be the earliest national mainstream publication to quote someone (in this case, a disgruntled serviceman) saying "That's for the birds!" A number of non-college newspapers in 1945 have matches for "for the birds," too—especially in the form "strictly for the birds."