Okay first let me say that in G/S the evolutionary stones are EXCEDINGLY rare. Once you beat the Johto Gym Leaders, you then have to beat the Elite Four and Champion Lance. Once you do that the credits will roll. Next time you start the game, walk out of your house and go to Professor Elm's lab to get the SS Ticket. Fly to Olivine City to catch the ship. After you land in Vermillion City, head north to Saffron and north again to Cerulean. Go to the sea cottage (Bill's house from R/B/Y). The old man wants to see sevral pokemon. One is Staryu. Show it to him to get the Water Stone.
I might say to you that Starmie is very difficult to get, and is not as good as Lapras anyway. Go catch a Lapras in Union Cave on Friday, they are much stronger than Starmie, and I imagin that by the time you do get the stone Staryu will be so high in level that Starmie will miss learning Confuse Ray.