Abstract: Binary black holes (BHBs) embedded in dense gas hold the promise of so-called "multi-messenger astrophysics": when they are detected both through gravitational waves (GWs) and electromagnetic (EM) observations, they will enable novel science.  This is true both for massive BHBs, whose GWs will be detectable by the future LISA satellite and by on-going pulsar timing arrays (PTAs), as well as for stellar-mass BHBs detected through ground-based GW detectors.  In both cases, identifying the coalescing binaries through their EM signatures will help clarify their astrophysical origin and yield novel probes of cosmology, fundamental physics, and accretion physics.  In this talk, I will describe how circumbinary gas may produce characteristic EM signatures for both massive and stellar-mass BHBs, based on analytic models as well as hydrodynamical simulations.  I will also argue that in both cases, some coalescing binaries may have already been detected in optical surveys, providing clues about their origin.