Binary stars are common. While only those with small separations may exchange gas with one another, even the widest binaries interact with their gaseous surroundings. Drag forces and accretion rates dictate how these systems are transformed by these interactions. We perform three-dimensional hydrodynamic simulations of Bondi-Hoyle-Lyttleton flows, in which a binary moves supersonically relative to a homogeneous medium, using the adaptive mesh refinement code FLASH. We simulate a range of values of the initial semimajor axis of the orbit relative to the gravitational focusing impact parameter of the pair. When the binary separation is less than the gravitational focusing impact parameter, the pair orbits within a shared bow shock. When the pair is wider, each object has an individual bow shock structure. The long-term evolution of the binary is determined by the timescales for accretion, slowing of the center of mass, and orbital inspiraling. We find a clear hierarchy of these timescales; a binary's center-of-mass motion is slowed over a shorter timescale than the pair inspirals or accretes. In contrast to previous analytic predictions, which assume an unperturbed background medium, we find that the timescale for orbital inspiraling is proportional to the semimajor axis to the 0.19 0.01 power. This positive scaling indicates that gaseous drag forces can drive binaries either to coalescence or to the critical separation at which gravitational radiation dominates their further evolution. We discuss the implications of our results for binaries embedded in the interstellar medium, active galactic nuclei disks, and common envelope phases.