If you know much about Chinese and Japanese cultures and the differences therein, it won't surprise you that fortune cookies were invented by a Japanese-American. The simplicity and yet intrigue of the shape is very, very Japanese, as is even the texture and the mild flavor meant to accompany tea. Check out a real Chinese bakery; you will see nothing remotely resembling a fortune cookie. Fortune cookies were probably invented by a Japanese/Japanese-American person for the Japanese Tea Garden in San Francisco and quickly adapted by savvy Chinese restauranteurs. As far as I know, no one really knows who precisely invented it, though a descendant claims it was Baron Makoto Hagiwara. (Well, heck, he has a cool name, so why not.)

I have read several alternate explanations, mostly from Chinese-American fortune cookie companies, that attempt to link fortune cookies to moon cakes and secret messages of yore. While there is probably some sort of cultural heritage thing going on (as usual) via the Japan-China link, this explanation sounds like a spurious marketing ploy or a sort of retcon attempt at cultural imperialism of sorts. (Usually it's the other way around--Japan has been historically fond of claiming everything from Chinese festivals to foods as indigenous and inventing histories wholesale to back up the claims.)

Now, this isn't to say there's something wrong with serving FCs in a Chinese restaraunt. There's a long-standing fascination with any kind of fortune-telling device in Chinese culture, and the messages one reads on them (when not TOO cheesy as above) are often fairly typical of various Chinese oracular devices. Plus, they go very well with jasmine tea.