Gravitational-wave (GW) recoil of merging supermassive black holes (SMBHs) may influence the co-evolution of SMBHs and their host galaxies. We examine this possibility using SPH/N-body simulations of gaseous galaxy mergers in which the merged BH receives a recoil kick. With our suite of over 200 merger simulations, we identify systematic trends in the behavior of recoiling BHs. Our main results are as follows. (1) While BHs kicked at nearly the central escape speed (vesc) are essentially lost to the galaxy, in gas rich mergers, BHs kicked with up to about 0.7 vesc may be confined to the central few kpc of the galaxy. (2) The inflow of cold gas during a gas-rich major merger may cause a rapid increase in central escape speed; in such cases recoil trajectories will depend on the timing of the BH merger relative to the change in vesc. (3) Recoil events generally reduce the lifetimes of bright active galactic nuclei (AGN) but may actually extend AGN lifetimes at lower luminosities. (4) Recoiling AGN may be observable via kinematic offsets (v > 500 km s^-1) or spatial offsets (R > 1 kpc) for lifetimes of up to about 10 - 100 Myr. (5) Rapidly-recoiling BHs may be up to about 5 times less massive than their stationary counterparts. These mass deficits lower the normalization of the M - sigma relation and contribute to both intrinsic and overall scatter. (6) Finally, the displacement of AGN feedback by a recoil event causes higher central star formation rates in the merger remnant, thereby extending the starburst phase of the merger and creating a denser, more massive stellar cusp.