Oppositely charged polymer–surfactant mixtures exhibit unique bulk and interfacial properties with many applications. In particular, cationic polymers paired with anionic surfactants are often used to deposit oils and lubricants on hair and skin upon dilution. These dilution-deposition systems are widely studied in simple mixtures but rarely in complex formulations. Thus, our paper focuses on cationic polysaccharides (cat-Guars and cat-HECs) paired with the anionic surfactant SLES-1EO (sodium laureth-1 sulfate) and incorporated into shampoos. We analyzed the polymer–surfactant complexes’ (PSCs) phase behavior, adsorption at the silicone oil/water interface, stickiness to bubbles (and drops), and deposition on hair-like substrates via phase behavior analysis, zeta potential measurements, foam film experiments, and imaging ellipsometry. Our results showed that the cat-Guar/SLES-1EO complexes exhibit wider precipitation regions and higher adsorption at the silicone oil/water interface than the cat-HEC/SLES-1EO complexes. Foam film experiments implied that only the cat-Guar/SLES-1EO complexes bridge the air bubbles (and silicone drops to hair) as they form sticky PSCs. Imaging ellipsometry revealed that cat-Guars deposit thick, inhomogeneous layers of PSCs and silicone on the hair-like substrates, whereas cat-HECs deposit thinner layers or nothing. Together, these findings elucidate the underlying deposition mechanism and offer strategies to optimize the polymer performance in shampoo formulations via a comprehensive experimental protocol.