A friend just gave me a Lee Valley sharpening kit that she had never gotten around to using. For lapping the waterstones, it includes a sheet of tempered glass, a sheet of adhesive-backed PVC laminate, and a vial of 90X silicon carbide grit. The PVC is to stick on the glass as a wearing surface, and for the grit to bed in. Lee Valley sell a 2oz. vial of the grit for $3.95.
Of course, people also use peel-and-stick sandpaper for the purpose. Anything coarser than the stone should work.
Brett, that reminds me of something I read on a woodworking site a while ago. Someone made a wooden cradle for his badly hollowed stone, then turned it upside down on the basement floor with a concrete block on top for weight. He then tied a rope from the cradle to his son's tricycle, and got the neighbourhood kids to take turns riding around dragging the device. Result: a nicely flattened stone without all that tedious rubbing.