All I had to do to evolve mine was to select the Water Stone and use it on Staryu. Be careful, though, because Starmie does not learn any moves by leveling up! If you want a glass cannon, I highly recommend you level up your Staryu until you get some powerful moves, then use the Stone.