We present detailed observations of the bright short-hard gamma-ray burst GRB 090510 made with the Gamma-ray Burst Monitor (GBM) and Large Area Telescope (LAT) on board the Fermi observatory. GRB 090510 is the first burst detected by the LAT that shows strong evidence for a deviation from a Band spectral fitting function during the prompt emission phase. The time-integrated spectrum is fit by the sum of a Band function with $\Epeak = 3.9\pm 0.3$\,MeV, which is the highest yet measured, and a hard power-law component with photon index $-1.62\pm 0.03$ that dominates the emission below $\approx$\,20\,keV and above $\approx$\,100\,MeV. The onset of the high-energy spectral component appears to be delayed by $\sim$\,0.1\,s with respect to the onset of a component well fit with a single Band function. A faint GBM pulse and a LAT photon are detected 0.5\,s before the main pulse. During the prompt phase, the LAT detected a photon with energy $30.5^{+5.8}_{-2.6}$ GeV, the highest ever measured from a short GRB. Observation of this photon sets a minimum bulk outflow Lorentz factor, $\Gamma\ga$\,1200, using simple $\gamma\gamma$ opacity arguments for this GRB at redshift $z = 0.903$ and a variability time scale on the order of tens of ms for the $\approx$\,100\,keV--few MeV flux. Stricter high confidence estimates imply $\Gamma \ga 1000$ and still require that the outflows powering short GRBs are at least as highly relativistic as those of long duration GRBs. Implications of the temporal behavior and power-law shape of the additional component on synchrotron/synchrotron self-Compton (SSC), external-shock synchrotron, and hadronic models are considered.