About once every 33 months, on average.
According to the "modern" definition, a blue moon is the second full moon in a month. This happens roughly seven times every 19 years, or once every 33 months, although the interval between blue moons will vary. (About once every 19 years a blue moon will occur twice in the same year.)
The "modern" definition, although widely accepted today, was originally a mistake. This mistaken definition was introduced in the March 1946 edition of "Sky and Telescope" magazine, and has been repeated by a variety of publications and news sources since, including the board game "Trivial Pursuit". (The magazine acknowledged the error in an article in their March 1999 edition.)
The "older" definition, first referenced in the "Maine Farmers' Almanac", refers to the third full moon in a season with four full moons. (Most seasons have only three full moons.) Why this would be important has to do with how one determines the exact date of Easter - a bit of trivia complex enough to warrant its own question. Interestingly, the "older" blue moon occurs about as frequently as the "modern" blue moon.
It should be pointed out that the term "blue moon" existed before either of these calendar based definitions came into vogue. It referred to an event very unlikely to occur, with roughly the same meaning as "when pigs fly" or "when hell freezes over".
WHO GOT IT RIGHT: Kathi Reynolds, Pete Daggett, Joe Pitsonbarger, Rick Gough, Marc Quinlivan, Marika Thiessen, Fred Holcomb, Denny Maxwell, Iron Saul, Marty Paul, Bob Milligan, and Randy Miller.