Well it's there, but there are other ways to find it.
You'll need pokémon with Surf, Dive and Thief or Covet. It's best that your Theif/Covet/Trick 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 hold, unless you're using Trick.
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/Trick. 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.