In defense of 5arx's initial association of the interjection "not!" with the Bill & Ted comedy franchise, I note this chronological listing in J.E. Lighter, Random House Dictionary of Historical American Slang (1997):
1991 Bill & Ted's Adventures (CBS-TV): Smooth move, dude! Not! 1992 M. Myers et al. Wayne's World (film): Wayne'll understand that right away. Not!
Still, as simchona points out, Wayne's World is generally credited with the resurgence in popularity of the usage—which in any case is more than 100 years old. In addition to the Princeton Tiger instance that simchona cites, Lighter notes such modern-sounding instances as these two:
1905 E.P. Butler, in Amer. Magazine (Sept.) 499: Cert'nly, me dear frind, Flannery. Delighted. Not! 1908 in Canemaker W. McCay 75: That confounded rarebit I ate...is making me sleep lovely. NOT!!!
You can confirm Lighter's findings in the Google Books entries for Ellis Butler's short story "Pigs Is Pigs" and for Mark Dunn, Zounds!: A Browser's Dictionary of Interjections (2005). Besides identifying the 1908 example as being from a Winsor McCay cartoon (presumably part of the Dream of the Rarebit Fiend series), Dunn points to an even earlier instance, by George Ade, that uses not similarly. From George Ade, "The Fable of What Happened the Night the Men Came to the Women's Club," in More Fables in Slang (1900):
Now Josephine was right there to see that Everybody had a Nice Time, and she did not like to see the Prominent Business Men of the Town dying of Thirst or Leg Cramp or anything like that, so she gave two or three of them the Quiet Wink, and they tiptoed after her out to the Dining Room, where she offered Refreshments, and said they could slip out on the Side Porch and Smoke if they wanted to.
Probably they preferred to go back in the Front Room and hear some more about Woman's Destiny not.
Another fairly early instance appears in Shirley Seifert, "The Nicest Boy and What the Smartest Girl in the Office Did to Him," in The Delineator (July-August 1920):
"Isn't it a cold night?" she [Kitty] said snippily to the gloomy, immaculate young man who called for her at eight the night of the party.
"So-so," said Benny, not committing himself.
"I think it's very warm myself," she said five minutes later.
"You just said it was cold," the young man reminded her. "Don't you know your own mind?"
"My, how polite you are—not!" said Kitty.