Early reionization changes the pattern of anisotropies expected in the cosmic microwave background. To explore these changes, we derive from first principles the equations governing anisotropies, focusing on the interactions of photons with electrons. Vishniac (1987) claimed that second-order terms can be large in a reionized universe, so we derive equations correct to second order in the perturbations. There are many more second-order terms than were considered by Vishniac. To understand the basic physics involved, we present a simple analytic approximation to the first-order equation. Then, turning to the second order equation, we show that the Vishniac term is indeed the only important one. We also present numerical results for a variety of ionization histories (in a standard cold dark matter universe) and show quantitatively how the signal in several experiments depends on the ionization history. The most pronounced indication of a reionized universe would be seen in very small scale experiments; the expected signal in the Owens Valley experiment is smaller by a factor of order 10 if the last scattering surface is at a redshift z similar or equal to 100 as it would be if the universe were reionized very early. On slightly larger scales, the expected signal in a reionized universe is smaller than it would be with standard recombination, but only by a factor of 2 or so. The signal is even smaller in these experiments in the intermediate case where some photons last scattered at the standard recombination epoch.