The phrasal verb (tr.) to gag for something originates with the verb "to gag", where a gag (n.) is:
[all quotes from the OED]
1.a. Something thrust into the mouth to keep it open and prevent speech or outcry; in Surgery, an apparatus for distending the jaws during an operation.
1553 T. Wilson Arte of Rhetorique 117 b Musicians in England have vsed to put gagges in childrens mouthes that they might pronounce distinctely.
1857 W. Collins Dead Secret II. v. ii. 105 If I only knew where to lay my hand on a gag, I'd cram it into your..mouth!
This explains the verb:
2.a. transitive. To stop up the mouth of (a person) with a gag in order to prevent speech or outcry; to put a gag into (the mouth) in order to keep the jaws distended.
1509 S. Hawes Pastime of Pleasure (1845) xxxii. 159 We saw men in great tormenting, With many ladies, that their mouthes gagged.
1886 W. J. Tucker Life E. Europe 195 He bound me, and then gagged my mouth.
1.b. intransitive. To choke, literal and figurative. Also, to retch. Also transitive (causatively).
?1706 E. Hickeringill Priest-craft: 2nd Pt. v. 49 I do not, in the least, wonder, that he (that swallows Transubstantiation) should Gagg at believing, that [etc.].
1963 M. Duggan in C. K. Stead N.Z. Stories 2nd Ser. (1966) 97 Suppose you gag a little at the sugar coating, its the same old fundamental toffee, underneath.
Now we come to be "to be gagging for" "to gag for" (which is the same as to be gasping for/to gasp for)
intransitive. to be gagging for: to be desperate for, to require urgently. Originally with reference to air; subsequently also (slang, chiefly British) more widely, esp. in sexual contexts. to be gagging for it: to be desperate for sexual intercourse.
1942 C. Mytinger Headhunting in Solomon Islands ix. 65 Both spinners have choked the engine liberally, with the result that if there is any gasoline at all the engine is gagging for air.
1990 Viz Dec. 45/5 Join the army cos all the birds are gagging for squaddies.
1998 Cycling & Mountain Biking Today Apr. 40/3 The best of the Brits are all gagging for a chance to show off their jumping skills.