We present the first direct magnetic field measurements on M dwarfs cooler than spectral class M4.5. Utilizing a new method based on the FeH band near 1 km, we categorize the integrated surface magnetic flux as low (well under 1 kG), intermediate (between 1 and about 2.5 kG), or strong (greater than about 3 kG) for a set of more than 20 stars ranging from M2 down to M9. Along with the field, we also measure the rotational broadening (v sin i) and Ha emission strength. Our goal is to advance the understanding of how dynamo field production varies with stellar parameters for very low mass stars, how the field and emission activity are related, and whether there is a connection between the rotation and magnetic flux. We find that fields are produced throughout the M dwarfs. In the mid-M stars, there is a clear connection between slow rotation and weak fields. In the late-M stars, rotation is always measurable, and the strongest fields are associated with with the most rapid rotators. Interestingly, these very cool rapid rotators appear to have the largest magnetic flux in the whole sample (greater than in the classical dMe stars). Ha emission is found to be a good proxy for magnetic fields, although the relation between the fractional emission and the magnetic flux varies with effective temperature. The drop-off in this fractional emission near the bottom of the main sequence is not accompanied by a drop-off in magnetic flux. It is clear that the methodology we have developed can be further applied to discover more about the behavior of magnetic dynamos and activity in cool and fully convective objects.