Binding and phase behavior of oppositely charged polyelectrolytes and surfactants with different chain lengths were studied in aqueous bulk solutions and at air-water interfaces. In particular, we have investigated the polyanion poly(sodium 4-styrenesulfonate) (NaPSS) and the cationic surfactants dodecyltrimethylammonium bromide (C12TAB), tetradecyltrimethylammonium bromide (C14TAB) and cetyltrimethylammonium bromide (C16TAB). In order to reveal the surfactant/polyelectrolyte binding, aggregation and phase separation of the mixtures, we have varied the NaPSS concentration systematically and have kept the surfactant concentration fixed at 1/6 of the respective critical micelle concentration. Information on the behavior in the bulk solution was gained by electrophoretic mobility and turbidity measurements, while the surface properties were studied using surface tension measurements and vibrational sum-frequency generation (SFG). This has enabled us to relate bulk to interfacial properties with respect to the charging state and the surfactants' binding efficiency. We found that the latter two are strongly dependent on the alkyl chain length of the surfactant and that binding is much more efficient as the alkyl chain length of the surfactant increases. This also results in a different phase behavior as shown by turbidity measurements of the bulk solutions. Charge neutral aggregates that are forming in the bulk adsorb onto the air-water interface - an effect that is likely caused by the increased hydrophobicity of CnTAB/PSS complexes. This conclusion is corroborated by SFG spectroscopy, where we observe a decrease in the intensity of O-H stretching bands, which is indicative of a decrease in surface charging and the formation of interfaces with negligible net charge. Particularly at mixing ratios that are in the equilibrium two-phase region, we observe weak O-H intensities and thus surface charging.