We present a theoretical model of two-component lipid membranes in close contact with a polyelectrolyte solution. Fluid mixtures of charged and neutral lipids as well as oppositely charged polyelectrolytes were considered, the lipids being allowed to redistribute themselves in order to maximize their interaction with the polymer. In the dilute regime the adsorption of a polyelectrolyte onto oppositely charged lipid surfaces induces lateral phase separation of the charged lipids, which form clusters near the polymer adsorption sites. On raising the polymer concentration to the semidilute regime (overlapping chains) the polyelectrolyte solution forms a homogeneous ionic background interacting with the membrane lipid heads. Naively one might guess that a redissolution of the clusters would then take place because of electrostatic repulsion and entropic effects. A mean-field model of the short-range polymer-surface interactions, augmented with the possibility of polymer lateral density variations, is proposed. We assume that only one kind of lipid can favorably bind to the polyelectrolyte, while the other ones do not exhibit any interaction with the polyelectrolyte. For ideal chains the model predicts the onset of slowly decaying attraction forces among nearby lipidic clusters which are simultaneously interacting with polymer chains (force proportional to (distance)(-2)). The force between lipid clusters is entropic in nature and is due to the deformation of the polymer density at the membrane-water interface. Inclusion of excluded volume effects greatly reduces the magnitude of the attractive forces which now decay exponentially. The model also suggests very slow kinetics for the clustering process, characterized by a long latency period followed by a burst in the aggregation rate when the process is near completion. Preliminary differential scanning calorimetry (DSC) measurements performed on lipid vesicles suspended in aqueous solutions of polyelectrolyte support the theoretical predictions, showing the onset of a permanent lateral phase separation in dilute polymer solutions which remains stable on further raising the polymer concentration to the semidilute or even concentrated regime.