The localization of the short-duration, hard-spectrum GRB 050509b was a watershed event. Thanks to the nearly immediate relay of the GRB position by Swift, we began imaging the GRB field 8 minutes after the burst and continued for the following 8 days. No convincing optical/infrared candidate afterglow or supernova was found for the object. We present a re-analysis of the XRT afterglow and find an absolute position that is ~4" to the west of the XRT position reported previously. Close to this position is a bright elliptical galaxy with redshift z=0.2248, about 1' from the center of a rich cluster of galaxies. Based on positional coincidences, the GRB and the bright elliptical are likely to be physically related. We thus have discovered evidence that at least some short-duration, hard-spectra GRBs arise at cosmological distances. However, while GRB 050509b was underluminous compared to long-duration GRBs, we demonstrate that the ratio of the blast-wave energy to the gamma-ray energy is consistent with that of long-duration GRBs. Based on this analysis, on the location of the GRB (40 +- 13 kpc from a bright galaxy), on the galaxy type (elliptical), and the lack of a coincident supernova, we suggest that there is now observational consistency with the hypothesis that short-hard bursts arise during the merger of a compact binary. We limit the properties of a Li-Paczynski ''mini-supernova.'' Other progenitor models are still viable, and additional rapidly localized bursts from the Swift mission will undoubtedly help to further clarify the progenitor picture. (abridged)