I have a few Shapton Professionals and have replaced ones I've broken with Shapton GlassStones. I also have a natural polishing stone. I flatten all of them with a Duo-Sharp 10" X 4" in grits 325/1200 ($100-$140). I use 325 for 2000 mesh and down (a 325 diamond WILL flatten a 220 waterstone) and flip it over to 1200 for my 4000s and up.
I read somewhere that Shapton likes to see a nice shiny surface on their polish stones. The 1200 provides that sheen on 4000 and up (I go to 16000 just for fun). DMT benchstones are also very flat thus they produce a flat surface on the waterstone.
You can "get by" with the other flattening procedures mentioned here; for the longest time I used the sandpaper/microfinishing method with good results. The diamond stones or diamond lapping plates are better . . . definitely better . . . here's why.
Flatness. If you lap on a flat surface, you get a flat stone. If the lapping surface is not flat, well, you're not really accomplishing anything, are you? Not to offend, but the flatter the better, and regardless of how good the mason is, a driveway, concrete block, or kitchen tile is not flat; at least not to the degree diamond bench stones and lapping plates are flat (BTW - For the flattest, Shapton Diamond lapping plates are the way to go. I didn't want to pay $300 - $500 for one, but have used them and they are great). In most cases, concrete is not even close to flat.
Concrete . . . ugh . . . Concrete and sandpaper can cause another problem - Clogging. The ceramic waterstones don't have this problem as much as natural, open-pore stones. Silicone Carbide and, to a greater extent, Aluminum Oxide are very friable and are the most common abrasive in sandpaper/lapping film. That's great because they break and leave sharp edges for greater abrasion as they are being used. HOWEVER, these broken pieces are much smaller than the whole and can clog pores in natural stones (all stones to some extent). Now on 2000 mesh and lower, this isn't a problem as you would be using pretty course sandpaper (400 grit and lower). The "broken" grains are still pretty big and don't really fit into the pores. However, trying to get the smooth sheen on polishing stones, using finer grit sandpaper is necessary, and those "broken" grains can and do get into the pores. Even more important than this is the loose resin used to hold the abrasive onto sandpaper. It's murder on polishing stone pores (can be washed off if very diligent). Diamond stones are basically graded diamonds in Nickel. The hardest material in the world is not nearly as friable as other abrasives and you're not going to be scraping off much Nickel in the flattening process - AKA not as much clogging.
Waterstones are not cheap, especially natural stones. However, if you take care of them (don't slide TWO off your workbench onto concrete and have to replace them

), they will last most of us for many years, if not a lifetime. If you're going to pay the money for good stones, pay the money for a good way to flatten them. I seriously got a chalky feeling in the back of my throat reading this thread and thinking about my $350 Suita even getting close to conrete for flattening purposes.
Diamond benchstones or lapping plates. If you don't want to spend the money, sandpaper on a flat surface (granite reference blocks are great) will work. If you choose this method, let me suggest 3M Microfinishing Film. This stuff is very consistent, has a much more durable resin bond, and lasts 10X longer than wet-dry (probably 3X longer than lapping film).
I get lazy and use a Lansky to sharpen my pocket knife. I don't recommend flattening Lansky Coarse and Medium Stones (buy new ones), but the ceramics and Arkansas stones can easily be flattened using the diamond plates on sandpaper, too.
My treatise on flattening,
cinteal