The phrase "gag me with a spoon" originates from Valley girl speak, which is in turn an obnoxious form of Californian english. From the wiki article:
Valley Girl (or Val, Val Gal) is a stereotype leveled at a socio-economic and ethnic class of American women who can be described as colloquial English-speaking, materialistic, self-centered, hedonistic, and often sexually promiscuous. Valspeak is also a form of this trait, based on an exaggerated version of '80s California English.
The phrase is used as an expression of disgust. A typical usage from the online slang dictionary
Oh my gosh, gag me with a spoon. That were the ugliest shoes I've ever seen!
The phrase also appears in Frank Zappa's song, Valley girl.
.../Its like grody.../ Grody to the max/ Im sure/ Its like really nauseating/ Like barf out/ Gag me with a spoon/ Gross/ I am sure/ Totally...
As for the how, you could perhaps reason that the act of gagging yourself with a spoon is pretty disgusting and hence it makes sense. However, I'm not sure you should look for a reason/proper etymology for any of the valley girl-isms (ummm, like, totally, so bitchin', whatever, etc.).