We present a detailed investigation of Hubble Space Telescope rest-frame UV/optical observations of 22 short gamma-ray burst (GRB) host galaxies and sub-galactic environments. Utilizing the high angular resolution and depth of HST we characterize the host galaxy morphologies, measure precise projected physical and host-normalized offsets between the bursts and host centers, and calculate the locations of the bursts with respect to their host light distributions (rest-frame UV and optical). We calculate a median short GRB projected physical offset of 4.5 kpc, about 3.5 times larger than that for long GRBs, and find that approx =25% of short GRBs have offsets of > ~10 kpc. When compared to their host sizes, the median offset is 1.5 half-light radii (re), about 1.5 times larger than the values for long GRBs, core-collapse supernovae, and Type Ia supernovae. In addition, approx =20% of short GRBs having offsets of > ~5re, and only approx =25% are located within 1re. We further find that short GRBs severely under-represent their hosts' rest-frame optical and UV light, with approx =30%-45% of the bursts located in regions of their host galaxies that have no detectable stellar light, and approx =55% in the regions with no UV light. Therefore, short GRBs do not occur in regions of star formation or even stellar mass. This demonstrates that the progenitor systems of short GRBs must migrate from their birth sites to their eventual explosion sites, a signature of kicks in compact object binary systems. Utilizing the full sample of offsets, we estimate natal kick velocities of approx =20-140 km s super(-1). These independent lines of evidence provide the strongest support to date that short GRBs result from the merger of compact object binaries (NS-NS/NS-BH).