We consider polyelectrolyte solutions which, under suitable conditions, phase separate into a liquid-like coacervate phase and a coexisting supernatant phase that exhibit an extremely low interfacial tension. Such interfacial tension provides the basis for most coacervate-based applications, but little is known about it, including its dependence on molecular weight, charge density, and salt concentration. By combining a Debye-Hückel treatment for electrostatic interactions with the Cahn-Hilliard theory, we derive explicit expressions for this interfacial tension. In the absence of added salts, we find that the interfacial tension scales as N-3/2(η/ηc-1)3/2 near the critical point of the demixing transition, and that it scales as η1/2 far away from it, where N is the chain length and η measures the electrostatic interaction strength as a function of temperature, dielectric constant, and charge density of the polyelectrolytes. For the case with added salts, we find that the interfacial tension scales with the salt concentration ψ as N-1/4(1-ψ/ψc)3/2 near the critical salt concentration ψc. Our predictions are shown to be in quantitative agreement with experiments and provide a means to design new materials based on polyelectrolyte complexation.