The self-similar propagation of optical beams in a broad class of nonlocal, nonlinear optical media is studied utilizing a generic system of coupled equations with linear gain. This system describes, for instance, beam propagation in nematic liquid crystals and optical thermal media. It is found, both numerically and analytically, that the nonlocal response has a focusing effect on the beam, concentrating its power around its center during propagation. In particular, the beam narrows in width and grows in amplitude faster than in local media, with the resulting beam shape being parabolic. Finally, a general initial localized beam evolves to a common shape.