In the mid-to-late 1920s, some of the pulp Science Fiction magazines (aimed at middle-class adolescent males interested in Science & New Inventions (The Coming Thing, at that time, maybe the beginning of The Technology Revolution) started publishing columns of their readers' letters, with their addresses). This led first to fans of the genre exchanging correspondence, then to the discovery that old mimeograph or ditto machines could often be found at a cheap price, and that you could send 8 pages of words for a three-cent postage stamp, thus communicating with several dozen people who shared your peculiar interests (you'd be lucky if you discovered as many as 2 or 3 such /w/e/i/r/d/o/s/ people in your geographic/social area).
These publications were called "fanmags" in the early days, but Louis Russell Chauvenet (who's still publishing) coined "fanzine" about 1942 and it became the common usage, sometimes abbreviated to "zine." (Like most social groups, "fandom" developed its own terminology ("fanspeak")—mostly by compression because stencils, paper, and postage cost money.) My impression is that neither of these words were derived from publications about movie stars, and that those came later, but that might be ethnocentrism.
My definition of "fanzines" (would you believe that there is some difference of opinion about the "proper meaning" of the word?) is usually something like: "Amateur, not-for-profit publications produced by and almost entirely for members of science fiction fandom" with care being taken to avoid even attempting to define "members" or "s-f fandom". (You'll notice that nothing is specified about the content having anything to do with science-fiction.) It's probably not a part of the definition, but they're traditionally almost always available for "The Usual" (coined by British fan Derick Pickles, probably in the '40s)—initially by request plus about enough stamps or cash to cover the cost, or one's own fanzine in trade, then for continued Trade, Letters of Comment (not necessarily to/on every issue), or occasional contributions of publishable material (including artwork).
I generally use 'Zines (with the initial apostrophe and upper case) to cover just about anything else that might be reviewed in Factsheet Five. Here, "The Usual" gets kinda dodgy—'Zinesters (often with an eye on newsstand/public sales) tend to be more ambitious and less likely to treat their publishing entirely as a money-sink hobby, and I'm comfortable with a Cash Payment requirement along the lines of an amount covering cost of printing and postage, rounded up to the next full dollar. (OTOH, I rather frequently find 'Zines that announce a "No Trades" policy to be uninteresting; I understand the financial and other constraints leading to this policy, but publishers who aren't much interested in what the readers are saying and doing tend to be a bit outside my sphere of appreciation & enjoyment.)
By the time I discovered this scene, about 1958, "(Science-Fiction fandom) Fanzines" frequently had little to do, directly, with "science-fiction" (or "fantasy," which is commonly lumped in with it); those of us who produced them had (for the most part) become more interested (at least for the purposes of publishing) in one-another, and in our other shared experiences, than in the genre that had spawned us. (Cf. Ruel Gaviola's account in Amusing Yourself to Death #9 of the Independent Literary Publishers Conference—add a few more social/personal details & snippets of conversation, assume that most of the readers are at least acquainted with most of the people mentioned, extend it to four or five pages, and you have a typical fanzine convention/party report.)
The above comments re fanzines ignoring sf aren't inaccurate, IMHO, but might be misleading—a fair number of old-time (& some newer) sf fans and fanzine editors & writers are still interested in the genre, and believe that good writing and stimulating ideation can be found there, and some do write about this in fanzines, but I suspect that most of us are more likely to talk about such things in person, at lit-oriented conventions or online (mostly in rec.arts.sf.fandom and *.written), if only because the field is now so broad that you can't any longer expect that most of the fans in a large group (say, the couple of hundred readers of a fanzine) have read or will read the same recent book, so in-depth discussions aren't common.
Addendum: Since writing this piece, I've discovered (though links in the E-zine Resource Guide) a whole bunch of amateur publications termed "Science Fiction Fanzines" that are not what I was writing or thinking about. They're from a daughter community, or a cadet branch of the family, perhaps, but seem to be so strongly oriented towards fiction based on TV & movie media sf, and sufficiently lacking in personal interaction and a broad scope of interests that it's difficult to think of them as part of the same family, other than that they're also DIY publications. For a sampling of the products of "Traditional Science-Fiction Fanzine Fandom" your best bet is probably Joe Siclari's site, Important Fanzines and Articles about Fandom. Joe is most interested in bibliography and the preservation of fanzines so old that even I find many of them more quaint than interesting, but he's keyboarded some of the more important of the older fan writings, and (more to the point, here) provides Links with most of the "Traditional style" fanzines and fanwriting that appear on Web Pages.

Reprinted from Amusing Yourself to Death, Issue 10. Posted with permission.