do you want an underwater tileset or a beach tileset? those are two different things
(http://nifflas.ni2.se/forum2/index.php?action=dlattach;topic=1276.0;attach=2745;image)
and theres a few good ones in the link Pumpkinbot gave you. (that's the public tileset bank, always try checking that first.)
as far as underwater, you can get creative with the standard tilesets (add bubbles around the screen for an underwater effect, etc.) i like using tileset 6 for that personally. i'm not sure if there's any made specifically for underwater scenes, since the basic ones are already pretty good for that.
if all else fails feel free to make one yourself. individuality is good :p
Well, what's wrong with these? I found one on Gaeels archive, and the other one on the old forum. I think both would work very well for this type of thing. No need to pay anyone.
(http://i39.tinypic.com/2use83l.png)
(http://www.gaeel-music.com/public/Ripen/beach%20and%20cave.png)