They're a little hard to obtain ~
You'll need pokémon with Surf, Dive and Thief or Covet. It's best that your Theif/Covet pokémon is pretty high level and that you carry a lot of Ethers or Leppa Berries around too to restore PP without having to go back to a pokémon centre. Don't give the pokémon anything to
First you need to get underwater - Surf out from Lilycove until you find a dark patch on the water - press A over it to Dive. Next find a patch of seaweed and run around in it - it's effectively the same as long grass.
Basically, you're looking for Clamperls with Blue Shards attached. When you find one, use Thief/Covet. If it had an item it'll let you know and it'll now be attached to your pokémon.
Take the Blue Shard to the collector new Mossdeep and he'll exchange it for a Water Stone.
Alternatively, ask someone with FireRed/LeafGreen to purchase you one from the Celadon Dept Store.
