According to New Scientist magazine, the way to win is to start with scissors.(Via BBspot.)
Research shows that stone, also called rock, is the most popular of the three possible moves in the game.
That means that your opponent is likely to choose paper, because they will expect to you to start the game with stone.
By going with scissors, you achieve an early victory.
Update: Regular reader Chris Zeh points out a problem with the New Scientist strategy:
It seems New Scientist's conclusion to the data is wrong. In my opinion if the most popular move is rock, then it has the highest probability of being thrown. If you throw paper you have the highest probability of winning, and if your opponent is aware of rock's popularity he will throw paper, producing a tie. This is favorable compared to losing your scissors to the majority throwing rock.I believe he is right. The NS strategy works if your opponent is aware of the fact that Rock is most popular, but believes that you don't already know that. And I don't know how often that will be the case.