Anisotropic gravitational radiation from a coalescing black hole binary is known to impart recoil velocities of up to ~1000 km/s to the remnant black hole. In this context, we study the motion of a recoiling black hole inside a galaxy modelled as an Hernquist sphere, and the signature that the hole imprints on the hot gas, using N-body/SPH simulations. Ejection of the black hole results in a sudden expansion of the gas ending with the formation of a gaseous core, similarly to what is seen for the stars. A cometary tail of particles bound to the black hole is initially released along its trail. As the black hole moves on a return orbit, a nearly spherical swarm of hot gaseous particles forms at every apocentre: this feature can live up to ~ 100 Myr. If the recoil velocity exceeds the sound speed initially, the black hole shocks the gas in the form of a Mach cone in density near each super-sonic pericentric passage. We find that the X-ray fingerprint of a recoiling black hole can be detected in Chandra X-ray maps out to a distance of Virgo. For exceptionally massive black holes the Mach cone and the wakes could be observed out to a few hundred of Mpc. Detection of the Mach cone is found to become of twofold importance: i) as a probe of high-velocity recoils and ii) as an assessment of the scatter of the mass-sigma relation at large black hole masses. ; Comment: 9 pages, 8 figures, new simulations added, accepted for publication in MNRAS