[Abridged] Recent numerical relativity simulations have shown that the emission of gravitational waves during the merger of two supermassive black holes (SMBHs) delivers a kick to the final hole, with a magnitude as large as 4000 km/s. We study the motion of SMBHs ejected from galaxy cores by such kicks and the effects on the stellar distribution using high-accuracy direct N-body simulations. Following the kick, the motion of the SMBH exhibits three distinct phases. (1) The SMBH oscillates with decreasing amplitude, losing energy via dynamical friction each time it passes through the core. Chandrasekhar's theory accurately reproduces the motion of the SMBH in this regime if 2 < ln Lambda < 3 and if the changing core density is taken into account. (2) When the amplitude of the motion has fallen to roughly the core radius, the SMBH and core begin to exhibit oscillations about their common center of mass. These oscillations decay with a time constant that is at least 10 times longer than would be predicted by naive application of the dynamical friction formula. (3) Eventually, the SMBH reaches thermal equilibrium with the stars. We estimate the time for the SMBH's oscillations to damp to the Brownian level in real galaxies and infer times as long as 1 Gyr in the brightest galaxies. Ejection of SMBHs also results in a lowered density of stars near the galaxy center; mass deficits as large as five times the SMBH mass are produced for kick velocities near the escape velocity. We compare the N-body density profiles with luminosity profiles of early-type galaxies in Virgo and show that even the largest observed cores can be reproduced by the kicks, without the need to postulate hypermassive binary SMBHs. Implications for displaced AGNs and helical radio structures are discussed.