Lay down some plastic and cover with paper (the thicker the better). Then, using lots on lots of paint decorate, either have a theme or just go graffiti style. an underwater theme worked well for us. Fishes and other watery pieces were painted on separate paper and card and placed on top.
paint brushes, other items to use as paint brushes, paint (lots) paper, tarps, cleaning up materials