History
Although VSEPR is often taught in conjunction with Lewis dot structures, it was actually developed independently -- Lewis dot structures were first introduced a half-century earlier. In the late 1950s, Gillespie and Nyholm were looking for a better way to teach molecular geometry to students. They noticed that some simple rules applicable to methane, ammonia and water also applied to numerous other molecules, albeit with some exceptions. Gillespie and Nyholm found that not only were these simple rules easier to teach, but the rules could be justified to some extent based on more sophisticated models. In 1957 they published an article explaining their ideas.
Rules
The great advantage of the VSEPR model is its startling simplicity. It assumes that electron pairs around an atom act as if they repel each other. Bonding pairs of electrons want to be as far apart from each other and lone pairs of electrons as possible. Lone pairs of electrons, however, take up more space, so the distribution of bonds around an atom is a little bit "bent" where a lone pair is involved.
Applications
If an atom has four bonds and no lone pairs, VSEPR predicts the bonds will arrange themselves around the atom in a tetrahedral pattern so the angles between all four bonds are equal. This is in fact exactly what is observed for methane. If an atom has three bonds and a lone pair, VSEPR predicts it will form a sort of pyramidal shape with the atom at the apex and the bond angles slightly below 109.5 degrees. This is in fact what is observed for ammonia. And if a molecule has two bonds and two lone pairs, VSEPR predicts a bent structure with a bond angle a little below 109.5 degrees for the two bonds -- which is in fact what is observed for water. VSEPR can be used to find the geometry of bigger molecules or atoms with 5 or 6 bonding &lone pairs as well.
Limitations
VSEPR has many limitations. It doesn't apply to certain molecules, especially complexes formed by transition metals. Nor is it possible to do calculations with VSEPR; you can get a rough idea of the shape but nothing more. Finally, VSEPR gives no information about how electron density is actually distributed. More sophisticated models like molecular orbital theory are required to determine how electron density is distributed around the molecule. Nonetheless, VSEPR is so conceptually simple you can use it to quickly work out molecular geometry in your head -- which is why it has been taught to generations of chemistry students and remains useful to this day.