The interaction between a flexible polymer in a good solvent and smaller associating solute molecules such as amphiphiles (surfactants) is considered theoretically. Attractive correlations, induced in the polymer because of the interaction, compete with intrachain repulsion and eventually drive a joint self-assembly of the two species, accompanied by partial collapse of the chain. Results of the analysis are found to be in good agreement with experiments on the onset of self-assembly in diverse polymer-surfactant systems. The threshold concentration for self-assembly in the mixed system (critical aggregation concentration, cac) is always lower than the one in the polymer-free solution (critical micelle concentration, cmc). Several self-assembly regimes are distinguished, depending on the effective interaction between the two species. For strong interaction, corresponding experimentally to oppositely charged species, the cac is much lower than the cmc. It increases with ionic strength and depends only weakly on polymer charge. For weak interaction, the cac is lower but comparable to the cmc, and the two are roughly proportional over a wide range of cmc values. Association of small molecules with amphiphilic polymers exhibiting intrachain aggregation (polysoaps) is gradual, having no sharp onset.