The earliest reference known to Wikipedia (as shared by jakebeal) is from 1956, but I found a few that were earlier.
First, perhaps a hint as to how this usage evolved, here's a mildly sarcastic 1919 reference about universities that have abandoned the ways of the Ivory Tower to offer such "practical" courses as plumbing and basket weaving (which presumably was a useful vocational skill in those days):
Higher education is becoming very practical indeed. It includes everything nowadays - excepting, of course, Greek and Latin - from plumbing to basket-weaving.
Source: "Studying National Parks," The watchman and southron. (Sumter, S.C.), August 06, 1919. link
The earliest usage I found that was specifically for "underwater basket weaving" is from 1953. It's in an article about slang used by the "younger generation" (implying that the usage is new, or at least new again):
Any snap course in school is "underwater basket weaving."
Source: "In a Hepster's Lingo, the Girl Who Likes to Neck is a Giraffe," Boston Globe, Oct 4, 1953, pg. A50
Throughout the 1950s, there are many references to "basket weaving" in the context of easy courses taken by student athletes.
Here's one such reference from 1952:
These may include courses in life-insurance salesmanship, bee culture, square-dancing, traffic direction, first aid, or basketweaving.
Source: "Magna cum nonsense," New York Times, March 16, 1952, SM68.
Here's a reference in a quote from one of these athletes, from 1953:
A varsity baseball player said he had received offers from San Francisco University guaranteeing him passing grades.
"I hardly would have had to go to classes," he said. "They told me I could major in basket weaving if I wanted to."
Source: "Other Schools Made Bids, Spartan Athletes Content," Newsday, March 3, 1953, pg. 50
The 1956 reference with "underwater basket weaving" that Wikipedia cites:
Why should he be given a better deal than those students who are attending college in order to get a "real" education ... majoring in underwater basket weaving, or the preparation and serving of smorgasbord, or particularly at Berkeley, the combined course of anatomy and panty-raiding?
Source: "College 'Pro' Football Hit," Los Angeles Times, June 4, 1956, pg A4
There's also many about plain "basket weaving" that year. For example:
Several schools screamed to high heaven about the fact that these so-called students, or at least the majority of them, couldn't pass the basket weaving examination and that their grade transcripts resembled those of the village idiot.
Source: "Cronin's Corner," Los Angeles Times, May 26, 1956, pg. B3
It was explained rather superciliously that they had a stiff struggle to get minimum passing grades in basket-weaving, musical appreciation or Loaf and Sleep (Letters and Science) courses.
Source: "Sports of the World," Atlanta Daily World, Nov 13, 1956, pg 5
I found these by searching ProQuest databases, the results unfortunately don't seem to include permanent links. Hence the lack of links.