Why do dianions (such as malonate) bind cations more strongly than anions?
This is known as the chelate effect. 

The main reason why you observe this is that cations in solution have an ordered solvent shell around them, especially in polar solvents where there will be defined solvent geometry around the shell; often octahedral for metal ions in water. The formation of a complex with a bidentate ligand such as malonate is more favourable than that with a monodentate ligand such as acetate because the same number of solvent ligands are lost with half the number of ligands complexed. This results in a greater increase in entropy - you can see this in terms of the degrees of freedom gained by the water molecules more than compensating for those lost by the new ligands.


  Is it simply because of the proximal availability of another $\ce{O-}$ group that can bind to cations ?


This is likely also a factor, although in most cases less important. In the case of the monodentate ligands there is a small energetic cost associated with bringing the anionic oxygen centres close to complex the metal centres. In the case of the bidentate ligand, some of this cost is "already paid" in the enthalpy of formation of the ligand - it is preorganized. This contribution becomes dominant for macrocyclic ligands.