We present initial results from the first systematic survey for Mg II quasar absorption lines at z>2.5. Using infrared spectra of 46 high-redshift quasars, we discovered 111 Mg II systems over a path covering 1.9<z<6.3. Five systems have z>5, with a maximum of z=5.33 --the most distant Mg II system now known. The comoving Mg II line density for weaker systems (W_r_<1.0{AA}) is statistically consistent with no evolution from z=0.4 to 5.5, while that for stronger systems increases three-fold until z~3 before declining again toward higher redshifts. The equivalent width distribution, which fits an exponential, reflects this evolution by flattening as z-->3 before steepening again. The rise and fall of the strong absorbers suggests a connection to the star formation rate density, as though they trace galactic outflows or other byproducts of star formation. The weaker systems' lack of evolution does not fit within this interpretation, but may be reproduced by extrapolating low redshift scaling relations between host galaxy luminosity and absorbing halo radius to earlier epochs. For the weak systems, luminosity-scaled models match the evolution better than similar models based on Mg II occupation of evolving cold dark matter halo masses, which greatly underpredict dN/dz at early times unless the absorption efficiency of small halos is significantly larger at early times. Taken together, these observations suggest that the general structure of Mg II-bearing halos was put into place early in the process of galaxy assembly. Except for a transient appearance of stronger systems near the peak epoch of cosmic star formation, the basic properties of Mg II absorbers have evolved fairly little even as the (presumably) associated galaxy population grew substantially in stellar mass and half-light radius.