Blue moon is a flavor of ice cream invented and popularized in the American north. It may have originated in Milwaukee, Wisconsin, and first appeared in the 1940s or 1950s. While the exact time and place remain a mystery, the biggest mystery is the flavor. Arguably, the defining feature of blue moon is its bright blue color, oft compared to Smurfs, and not the flavor at all.
The flavor is, to say the least, elusive. It is fruity and marshmallowy, and is sometimes compared to Froot Loops. Attempts to mimic the flavor often use vanilla, almond extract, pineapple extract, raspberry flavoring, and lemon oil.
While this treat has traditionally been most popular in the states abutting the Great Lakes (and, strangely, Virginia), it is not unheard of in most of the Eastern US and Midwest. In some places it is best known as one of the colors used in Superman ice cream (a mix of blue, red, and yellow ice cream; again, the colors are more important than the flavors). It has also made its way overseas, where it is often sold as the local translation of "Smurf ice cream", although Studio Peyo, which owns the copyright to the Smurfs, have been working hard to end this practice, and most established European vendors have switched over to other names, e.g., the German Himmelblau, meaning 'sky blue'.
The Chicago Tribune did an excellent story on the possible origins of Blue Moon ice cream, which provided much of the information for this writeup.