The synergistic adsorption and complexation of polystyrene sulfonate, PSS (a highly charged anionic polyelectrolyte), and dodecyltrimethylammonium bromide, C(12)TAB (a cationic surfactant), at the air-water interface can lead to interfacial gels that strongly influence foam-film drainage and stability. The formation and characteristics of these gels have been studied as a function of PSS molecular weight by combining surface tension, ellipsometry, and foam-film drainage experiments. Simultaneously the solution electromotive force has been measured to track the polymer-surfactant interactions in the bulk solution. It has been found that there is a critical molecular weight for surface gelation as well as for bulk precipitation and aggregation. Furthermore, we show that for the lowest molecular weights, PSS adsorbs with C(12)TAB in compact layers at the air-water interface. In particular, for mixtures of C(12)TAB with the monomer compound of the PSS repeat unit (e.g. M-w = 208), interfacial complexation is found to be similar to that of catanionic mixtures (mixtures of surfactants of opposite charge).