The suggestions below were from PUBYAC contributors. If you're a member check out the archives for 7-19 & 7-21-2010. If you have any other suggestions, please add.
For more offerings, see: Storytime-Beach; Sea & Seashore
"Sponge Bob Squarepants" Get a selection of sponges at Wal-Mart and cut them in half, (they could be also be cut in 4ths for miniature Sponge Bobs). Pre-cut colored pipe cleaner arms and legs to stick in the sides. Put out scraps of colored paper (construction, wallpaper, etc.) for the kids to cut into hair and clothes. Use "eyeball stickers" for eyes and draw on mouths with permanent marker, (cut paper can be used for that also). Elmer's glue probably works best.
Some of the sand ideas:
use glue and sand to draw or outline castles or ocean creatures.
create an ocean scene in a shoebox lid, or using a blue plate as the back and a clear plate as the front.
cut contact paper into sea-shapes, or put it in the middle of a shaped 'frame' and sprinkle with colored sand.
cut castles out of sandpaper and let the kids decorate.
Other ideas: