It seems to have first appeared in 1956 when both the Cadets and the Jayhawks charted with the tune Stranded In The Jungle. Why we had two bands running about screaming this, I know not. It was apparently due to the efforts of these bands that this phase came to the attention of one Frank Zappa. Still, it came and it went, as is the case with many pop cultural oddities. (slap bracelets anyone?)
After a brief hiatus, the zeitgeist was again assaulted with googly and moogly of great stature in 1961 by Howlin' Wolf in Goin' Down Slow.
Not to have rest upon its laurels, this phrase sought even more note through association with a presidential candidate of days gone by, Alfred E. Neuman. The 1960's saw the MAD Magazine universe use this is something that a Tarzan-esque lad would utter. Seems a bit sophisticated for king of the jungle, but those were halcyon days...
After having had a busy time of it, the phrase seems to have taken a leave of absence through most of the late 60's, only to reappear in 1973, courtesy of the infamous Frank Zappa. It is uttered in the medley collectively known as Don't Eat the Yellow Snow. The portion containing the phrase pirated by the man to hawk candy bars is Nanook Rubs It. Rub it Nanook, rub it.
And this is how a great phrase has come to be defiled, its varied history lost... The only taste left in our mouths being that of chocolate, caramel, peanuts and nougat ... somehow rather unsatisfying...