Interesting. I wonder how I missed that when I was checking this for alternating groups. So, clearly commutativity is not enough to deduce that product of two central involutions is also central. Can you think so some other conditions that will suffice? Some famous examples of groups where this sort of closure is true and used are $J_2$ and $Suz$.

Kindly note that I am interested in only those conjugacy classes of involutions which contain a central involution. Since conjugate of a central involution is also central, it would mean that the conjugacy class would consist entirely of central involutions.

Yes, I didn't notice that it is quite straightforward to show that the result is true if G has a unique conjugacy class of involutions. I am slightly rephrasing the question now. @ColinReid: I was talking about conditions on G and not the part of the statement following "if and only if"

A great follow up to that: arxiv.org/pdf/1305.2584.pdf

I should point out that the dancing links algorithm of Knuth (sagemath.org/doc/reference/combinat/sage/combinat/matrices/‌​…) works pretty well for small cases.

Thank you. This seems helpful. I will try to see how well it works in my particular problems. I am sure I can exploit the symmetry as well.

It's only for those cases, the so called thin geometries, where it amounts to finding perfect matchings. I had posted another question regarding that earlier (mathoverflow.net/questions/168241/…). But in more general cases it doesn't reduce to finding perfect matchings.

@NoamD.Elkies: Thank you for pointing it out. I should have put a better example. The particular ones that I am working with are generalized polygons. For example, if you look at the flag geometry of classical projective plane of order $q$ then you get a generalized hexagon of order $(q,1)$ which certainly has such a solution (corresponding to a perfect matching in the incidence graph of the projective plane).

@MichaelZieve: I have edited the question details again. Hopefully this is the last edit.