This phrase is widely known as a Chinese expression, and is said to be a curse. Some sources describe it as an Egyptian or, as someone in this node stated, Scottish expression. The consensus is that it's Chinese. Several sources declare it to be but part of a longer expression, "may you live in interesting times and come to the attention of important people." Regardless to whom it's attributed, it's a mildly popular phrase used by the press, in literature, and in industry reports whose compilers' style guide tells them to commence with ancient wisdom and platitudes. Terry Pratchett's Interesting Times is probably the cause of the current and ongoing revival of its use.
All fine and well. Until you ask a Chinese scholar, that is. Or any native Chinese-speaker. Torrey Whitman, president of the China Institute in New York and said to be a bit of an authority on Chinese proverbs, was asked about it, and here's what he is quoted as saying in response:
"...what is most noteworthy about the expression is that it is not Chinese. There is no such expression, "May you live in interesting times," in Chinese. It is a non-Chinese creation, most probably American, that has been around for at least 30 or 40 years. It appears in book prefaces, newspapers (frequently in the New York Times) and speeches, as an eye- or ear-catcher, although I have not found it in Bartlett's Quotations or other quotation sourcebooks. I speculate that whoever it was who first coined it attempted to give the expression a mystique, and so decided to attribute it to the Chinese."
The first time I encountered this phrase was in Frank Herbert's The Godmakers, where I'd say it's used as a warning rather than a curse. This book was published in 1973 and probably contributed to the spread of the expression, something which would hardly be unusual for a prolific meme-generator like Herbert. I also find it to be quite consistent with this author's penchant for inventing and using obscure, ambiguous and profound-sounding sayings. Mr. Whitman may not be far off the mark.
As it turns out, this, too, is a nice theory but not true, except for the part about Whitman being on the mark. A habitual phrase-hunter by the name of Stephen Delong turned the quest for the phrase's origin into a life goal and came up with a lead for a story called U-Turn written by Eric Frank Russell (under the pseudonym of Duncan H. Munro) for the April 1950 issue of Astounding Science Fiction. In this story the phrase is described as an old Chinese curse turned modern-day blessing. Whether Herbert knew of it or not is debatable but likely given that quite often the audience of sci-fi writers was other sci-fi writers. It's highly likely that he added to whatever popularity the phrase had acquired before the 1970s.
What does remain true about the above theory is the science fiction connection. Herbert of course, who seems to prefer very un-Chinese, Middle Eastern cultural references, must have added to the confusion by incorporating it into his work even if it was in use earlier. There is also a recorded speech from 1966 in which Robert F. Kennedy uses the phrase. The trail runs cold while trying to trace it back to Carl Jung in 1931, and I'll consider this false unless I get my hands on the German original of the text cited and see otherwise. The English translation does not contain the saying.
Wikipedia's current wisdom on the topic states that an early occurrence of the phrase is found in the memoirs of Hughe Knatchbull-Hugessen, His Majesty's ambassador to China in the late 1930s. Indeed, this does appear to be the case bright and early on page ix. These memoirs were published in 1949. (Sir) Austen Chamberlain, Nobel peace laureate and elder half-brother of the appeaser-in-chief, is cited as having used the phrase in his correspondence, apparently attributing it to a British diplomat "many years ago." That was in 1936. I'd have to see that one. Since Chamberlain was quoted posthumously, he was not around to correct that particular author's memory. Phrased like that, Knatchbull-Hugessen can not have been his source since he was ambassador in 1936/7 and also attributes it to someone else. Perhaps Knatchbull-Hugessen and Chamberlain had the same source. I'll grant that Russell may not have been the originator but would suspect that he came across the saying independently and without the aid of the British diplomatic corps.
The phrase is one that sticks in the reader's mind and could easily have been adopted by numerous smart alecks who proceeded to employ it in casual conversation. When used by people unfamiliar with its origin, it's easy to attribute a saying to some ancient school of wisdom, in which case Confucius, anonymous Celts, and long-dead pharaonic scribes serve the purpose admirably. I'll add my own, more substantiated, speculation to everyone else's and put forward the idea that it is, beyond reasonable doubt, contemporary, and all other theories are science fiction... or rather, the saying itself could well be science fiction and the colourful ethnography surrounding its origins is a myth.
Interesting.
References:
http://lalaland.cl.msu.edu/~vanhoose/quotes/0010.html
http://www.chinasprout.com/html/column15.html
http://hawk.fab2.albany.edu/sidebar/sidebar.htm
http://www.rfksa.org/speeches/speech.php?id=1
Special thanks to alfimp