Greetings all. So far we've got a whole lot of links to and quotes from Wikipedia. Just a reminder to anyone considering responding that answers consisting only of a link, or relying on tertiary sources like Wikipedia are not permitted in this sub: this is AskHistorians not AskRedditorstoGoogleThatForMe. Thanks!

James I Deutsch of the Smithsonian has what I believe to be about as good an answer as you're going to get. In his entry on the game in The Encyclopedia of Play in Today's Society he suggests that:

The origins of Rock Paper Scissors remain obscure, in part because there are neither tangible artifacts nor written documents typically associated with the game. nevertheless, there is evidence that a similar finger-throwing game (in which two players simultaneously display a number of their fingers) was played in Egypt as early as 2000 BCE. The idea of three distinct gestures made with the hand and fingers seems to have emerged in eastern Asia by 2000 BCE, where each gesture represented one of three competing entities.

The "entities" varied - he lists snakes, frogs, elephants, etc - but notes that rock, paper and scissors had become the dominant variant in Europe by the mid 1700s.

I'd love to know what Deutsch's sources are on the game in ancient Egypt or on the Rochambeau thing, but it's impossible to tell where he got that info from the article I'm afraid.

Edit: /u/ThomasTTEngin's comment turned me on to a blog post in which John Beuscher posits a quite different theory about the origins of the game here

I did a rather tedious search in online databases of books, periodicals, and newspapers published in America from the 17th- through 19th-century and found absolutely no mention of "Rochambeau" used as the name of a game, or, for that matter, of any mention of Rochambeau playing rock-paper-scissors, or even any mention of the game of rock-paper-scissors itself being played in America at all until well into the 20th century. I certainly do not believe that my search has been exhaustive (many old newspapers are not online, for example), and there was plenty that was written that was never published, but if the game was being played by children of European descent "from time immemorial," it seems odd (but not conclusive) that I have been able to find no one mentioning it in anything published in America for the first several centuries of European presence here, even though the game, by its very nature, is not something on which writers would necessarily have thought to expend much ink, if they deigned to notice it at all.

So two conflicting theories there - I guess this ultimately comes down to which historian you trust more. Unless someone here has done original research on this I'm not sure how easy it will be to tell which one is right. Such is history!

As an add on to this question, why did the game become so popular in japan? I dont know about other asian cultures, but its everywhere in japan, and ive never understood why. Is it something that was introduced after ww2, or does it go back farther?

The book Korean Games with Notes on the Corresponding Games of China and Japan published in 1895 by the Director of the Museum of Archaeology at the University of Pennsylvania suggests the game was East Asian at that time. The game is listed among a range of indigenous east asian games without any suggestion it is anything other than exotic to an American audience.

https://archive.org/stream/cu31924023272424/cu31924023272424_djvu.txt

It seems prior to that, the origins of the game are something of a mystery.

Rock, paper, scissors (jan-ken) is actually one of the last surviving members of a larger family of Japanese games called sansukumi-ken. Sasukumi-ken games all share the same pattern of having three different gestures that compete against each other. The earliest of these games is mushi-ken (mushi means "small animal") that consists of gestures representing a snail, a snake, and a frog. Mushi-ken and other ken games likely originated from China. At the beginning of a ken tournament, the referee is expected to give a speech describing the history of ken game from the time of the "wise kings" of China to when ken games arrived in Japan through Nagasaki.

There are other extinct variants of sansukumi-ken games. In fox-ken, the three gestures are kitsune (supernatural fox), the head of a village, and a hunter. In tiger-ken, the Japanese-Chinese pirate hero Watonai (known in Chinese as Coxinga) is represented by one of the gestures. The two other gestures are tora (a tiger) and Watonai's mother.

Sepp Linhart wrote a very detailed history of sasukumu-ken in the chapter From Kendo to Jan-Ken: The Deterioration of Game from Exoticism into Ordinariness. More importantly, unlike some of the tertiary sources that have been cited so far in this thread, Linhart provides primary sources on the history of rock, paper, scissors. A preview of the chapter is partially available online for those interested in reading it.

Linhart, Sepp, and Sabine Frühstück. The Culture of Japan as Seen through Its Leisure. Albany: SUNY Press, 1998. Print.