Originally, a promotion for an ice cream parlor (I really cannot find any firm proof who did this first; it may have been Baskin-Robbins, who seem to be best known for doing this, but even they don't claim to have been the first. One site notes Magnolia Ice Cream company in the Philippines doing it back in the 1960s; no other source I can find gives a start date.) The promotion would involve a particular flavor of ice cream that would only be available during a particular month, such as "Trick-Oreo-Treat" during October. The idea caught on for not only ice cream shops, but any other product which came in different flavors and could promote one per month.

From this came the modern use of "flavor of the month" to describe any fad which is currently popular but not expected to last very long, or sometimes just something that has very recently become popular: "If you've just sold a spec script, directed a critically acclaimed debut feature, or starred in a well-received low budget film, you're the flavor-of-the-month: nobody knows who you are, everyone wants to meet you, and you could spend the next three months taking meetings and getting lots of free food." (Wordplayer)

Sources:
http://www.fsmarketing.com/fsm/novdec01/fsmnovdec01-bs1.shtml
http://www.peterschocolate.com/industry/increasesales.html
http://www.baskinrobbins.com/treats/flavor_month.shtml
http://www.baskinrobbins.com/about/corp_news.shtml
http://www.foodpeople.com.ph/reviews2.htm
http://www.wordplayer.com/columns/wp16.Tinsel-speak.html
http://wordsmith.org/awad/archives/0402
http://www.flipperdave.com/fliptionary.html