The origins of the phrase is derived from the practice of forcing oneself to vomit, a typical trait of bulimia nervosa. The sufferer will often use their own fingers or a long narrow instrument to induce vomiting; e.g. a spoon handle.
How to Identify Symptoms of Bulimia
Look for evidence of laxatives in your home. Many teens purge through
the help of laxative abuse. They also purge by sticking their fingers
or other objects down their throat. Look for the presence of spoons or
other objects that don't belong in a bathroom for signs of this.
Borderline Personality Disorder: New Reasons for Hope
By Francis Mark Mondimore, Patrick Kelly
The hallmark of bulimia is binge eating, during which persons eat
enormous amounts of food, often high-calorie foods, over a period of
an hour or so [...]When a person who has bulimia cannot force another bite, she is overcome with disgust and shame at what she has done and seeks a way to rid herself of the calorie load. the vast majority of persons ... do this by forcing themselves to vomit. [...] Individuals with bulimia usually stimulate their gag reflex by putting a finger or spoon down the throat in the early stages of their disorder but often become adept at vomiting at will.
Despite the Ngram's chart's display which suggests the phrase predates the 80s, the earliest recorded usage of this Valleyspeak I could find were dated 1980 and 1981 respectively.
Air Force Driver, Volumes 14-16
Like barfme out; gag me with a spoon. “Oh migosh! I'm getting a used
four-wheel-drive. That's going to be like really, like a lot of money
- I'm freakin' out, I'm sure. But, I don't know; like it's going to be like so cool, you know. Like see my 4X4.
and The William and Mary Review, Volumes 19-22
"I love you," said Justin Oligarchy "Gag me with a spoon," said Eunice
Babel absently, looking again to Joseph Beaumont Darrow IV Two fire
trucks roared up to the Auditorium, their sirens wailing. "What's the
trouble here?"
A very well written piece charting and explaining the "rise and fall" of this expression, forever linked to the 80s, is in the article Gag Me With a Spoon: “Val-Speak” Takes Over SoCal by Jennifer Ouellette
Frank Zappa’s quirky Top 40 hit from 1982, “Valley Girl,” doesn’t get
much radio airplay these days, even on the “nostalgia” stations, but
it captured the birth of a linguistic phenomenon in the running
commentary provided by his daughter, Moon Unit — “val-speak,” a
strange dialect spoken by the female denizens of the San Fernando
valley area in Southern California characterized by ending sentences
with a slight rise in pitch, as if asking a question, now known as
“uptalk.” And it might have stayed in the Valley, too, if it weren’t
for that meddling musician and his daughter, who broadcast it to the
masses. Soon everyone was walking around declaring their school
lunches were “grody to the max,” I mean, “gag me with a spoon,” every
uptalking utterance punctuated by frequent insertions of “like” and
“totally.”
Source: Scientific American.com