The first one on record came from Tokyo in 2003, but probably the most notable early work was Koizora (Love Sky), published in 2005. A semi-autobiographical romance, it spawned a film, a television drama, and a manga series, as well as being picked up by a traditional publisher to be put out as a two-part paperback and earning a long article in that most prestigious of cultural bastions, The New Yorker.
Like most of its genre, Koizora was originally published to a website that aggregates them, posted from the author's cell phone, received by readers in SMS messages. Chapters were generally 70-100 words, to fit within character limits.
It was also free, as are most. Keitai Shousetsu are about sharing your story and getting it read - connecting with fans, which is one of the motivating factors behind Creative Commons. Using free media to connect to readers worked well for a lot of Japanese authors of cell phone novels: in 2007, 5 of the 10 bestselling novels in Japan started life as cell phone novels.
Part of the reason for the popularity of them is that the authors knew how to connect to their audience: their target readers are cell phone-savvy teenagers interested in upcoming trends and romance. There was also a shared culture of anonymity: most authors of Japanese cell phone novels go by handles and are never known by their real names.
The mobile culture in Japan and other parts of East Asia is one of the reasons cell phone novels have taken off there. In contrast, the highest-viewed cell phone novel in the US has had a mere 30000 views.
Part of the difference is that we're used to longer chunks in Western culture: fans of George R. R. Martin were utterly outraged when his latest novel was delayed. Some of the serial stories I read publish only in several-thousand-word chapters. Cell phone novels or Twitter novels require a shift in thinking, a willingness to let things unfold at precisely the author's pace.
But RSS feeds for continuing stories and places like Wattpad are making serial fiction more viable in the Western world, or at least to Western writers: polylingual East Asian readers are still a huge portion of the audience on Wattpad.
The literary and cultural scene continues to evolve rapidly, making this an exciting time to be in writing and publishing.