The prevailing wisdom1 is that the term "waifu" originates from a scene from the 2002 anime Azumanga Daioh; specifically, this scene from episode 15.
Some context: the male character in that scene, Mr. Kimura, is a teacher at the school the female characters in that scene attend. Mr. Kimura has a well-deserved reputation for being generally perverse and possibly a pedophile.
A rough translation of the scene follows:
TAKINO Tomo: What's this? A picture of a woman?
KASUGA Ayumu: Wow, she's beautiful.
TAKINO Tomo: Who is she?
KIMURA: My wife.
All: That can't be!
The astute listener will observe that Kimura uses the English words "my wife", rather than a Japanese translation thereof (such as 妻2 tsuma). When the words "my wife" are adapted to conform to Japanese phonological constraints (e.g. no terminal /f/), and then re-expressed in a Japanese syllabary (hiragana/katakana), the result is マイワイフ. Finally, when we romanize マイワイフ, we get "mai waifu".
The below graph shows that usage of "waifu" on the internet was effectively negligible until early 2007. This seems to suggest that "waifu" did not become memetic until some time after Azumanga Daioh aired.
There is evidence from the Animesuki forums that "waifu" (in fact, "mai waifu") was being used in its modern sense (rather than the literal standard-English "woman one is married to" sense) by May 2006. Interestingly, this appears to precede the rise in searches for "waifu" on Google Trends. I'm not sure what this means, but it probably means something.
There is also a male counterpart to "waifu": husbando. Unlike "waifu", "husbando" is not derived from Japanese3. Rather, it was developed by analogy, as an idealization of how a Japanese speaker might pronounce the word "husband". A "husbando" is basically the same thing as a "waifu", except male rather than female.
The earliest citation I've found for "husbando" is from October 2007 (again, on Animesuki). With some internet archaeology, I suspect it should be possible to show that usage of "husbando" began as much as a year prior to this citation.
1 I say that this is the prevailing wisdom, because I have no evidence that "waifu" was not used prior to 2002.
2 The Japanese equivalent of "mai waifu", in terms of usage among otaku and memeticity and so forth, is actually 俺の嫁 ("ore no yome", lit. "my bride").
3 ハズバンド hazubando exists, but I'm almost certain this didn't directly give rise to English "husbando". At most, it may have been an inspiration.