You can interactively play with a basic Voronoi diagram at http://mbostock.github.com/d3/ex/voronoi.html. The yellow polygon on the mouse shows the polygon that would be there if there had also been a point underneath the mouse cursor. That demo helped me get a feel for how they work.

If you're skimming, don't miss this article's Flash demo linked at the bottom, http://www-cs-students.stanford.edu/~amitp/game-programming/....