According to Newsvine in 2007, the phrase has been prevalent for 15 years, so that's 17 years now. The general consensus in forums/sites I've searched is that the phrase was first used in Wayne's World (1992).

From the movie:

Garth Algar: Hey, are you done yet? I'm getting tired of holding it.
Wayne Campbell: Yeah, that's what she said.

http://www.youtube.com/watch?v=Fo5lg_Jl2p8

I was actually having a conversation with my friend the other day about this after watching the office. Here's what I found.

"While we may never know the exact origin of the phrase, one of the earliest, if not first, occurrences of "That's what she said" in popular culture can be traced back to 1992 in the SNL sketch-turned-film, Wayne's World:

Garth: Hey, are you done yet? I'm getting tired of holding it.
Wayne: Yeah, that's what she said.

As far as one of the first people to have first said it we have traced back to Philadelphia were Neil Cohen was making that's what she said remark at is place of employment at Asian World of Martial Arts as early as 1988. "

http://www.youtube.com/watch?v=BLfwl9QP294

Professor Theodore I. Lkbls (of fairly uncertain origin himself) proposes that the "that's what she said" joke actually started when someone told a serious person something that she, in fact, did say. His theory is that it originated in some backwater college where a decidedly unintelligent person said something to the effect of, "Hey, dude, where'd the universe come from?" He was, as you may have guessed, a stoner. Anyway, the professor who's half-a-brain was still intact replied, "Why, that was the Big Bang." The stoner, whose name has been postulated to be John Smith, or possibly John Doe, saw an opportunity for the cheapest laugh he could get, but hey, he was a stoner, so who cares? He thought "Mothher Erth will findd thihis funnie"sic and so said "That's what she said." No one laughed except Smith/Doe, who found it so funny that he did it again and posted the event on YouTube. No one paid it any mind until some liberal minded politician caught wind of it. He began speaking out against this form of "disgusting exploitation" of the children who "simply want an education."

I HOPE I HELPED!!! :)