We report on the gamma-ray activity of the blazar Mrk 501 during the first 480 days of Fermi operation. We find that the average LAT gamma-ray spectrum of Mrk 501 can be well described by a single power-law function with a photon index of 1.78 +/- 0.03. While we observe relatively mild flux variations with the Fermi-LAT (within less than a factor of 2), we detect remarkable spectral variability where the hardest observed spectral index within the LAT energy range is 1.52 +/- 0.14, and the softest one is 2.51 +/- 0.20. These unexpected spectral changes do not correlate with the measured flux variations above 0.3GeV. In this paper, we also present the first results from the 4.5-month-long multifrequency campaign (2009 March 15 - August 1) on Mrk 501, which included the VLBA, Swift, RXTE, MAGIC and VERITAS, the F-GAMMA, GASP-WEBT, and other collaborations and instruments which provided excellent temporal and energy coverage of the source throughout the entire campaign. The average spectral energy distribution of Mrk 501 is well described by the standard one-zone synchrotron self-Compton model. In the framework of this model, we find that the dominant emission region is characterized by a size <~ 0.1 pc (comparable within a factor of few to the size of the partially-resolved VLBA core at 15-43 GHz), and that the total jet power (~10^{44} erg s^{-1}) constitutes only a small fraction (~10^{-3}) of the Eddington luminosity. The energy distribution of the freshly-accelerated radiating electrons required to fit the time-averaged data has a broken power-law form in the energy range 0.3GeV-10TeV, with spectral indices 2.2 and 2.7 below and above the break energy of 20GeV. We argue that such a form is consistent with a scenario in which the bulk of the energy dissipation within the dominant emission zone of Mrk 501 is due to relativistic, proton-mediated shocks.