We present the first proper motion measurements for the galaxy M31. We obtained new V-band imaging data with the HST ACS/WFC and WFC3/UVIS of a spheroid field near the minor axis, an outer disk field along the major axis, and a field on the Giant Southern Stream. The data provide 5-7 year time baselines with respect to pre-existing deep first-epoch observations. We measure the positions of thousands of M31 stars and hundreds of compact background galaxies in each field. High accuracy and robustness is achieved by building and fitting a unique template for each individual object. The average proper motion for each field is obtained from the average motion of the M31 stars between the epochs with respect to the background galaxies. For the three fields, the observed proper motions (mu_W,mu_N) are (-0.0458, -0.0376), (-0.0533, -0.0104), and (-0.0179,-0.0357) mas/yr, respectively. The ability to average over large numbers of objects and over the three fields yields a final accuracy of 0.012 mas/yr. The robustness of the proper-motion measurements and uncertainties are supported by the fact that data from different instruments, taken at different times and with different telescope orientations, as well as measurements of different fields, all yield statistically consistent results. Papers II and III explore the implications for our understanding of the history, future, and mass of the Local Group. (Abridged)