The key is to imagine people as complex individuals and not a check-list of organic criteria and stereotypes. The human experience is subjective to culture in a big way but EVERYBODY feels at odds with that, too. Black, white, men, women - we all feel a connection to certain ideas of who we are but also at odds with how we think we should be and how we think others see us. The spectrum of emotions and confusion connects us all.
I find it easier not to write about men and women but to write about people. Once you're past that obstacle, you can then find a more social distinction in characters with what you know and what you have experienced in your life interacting with a variety of people.
The quote really should be "Whoever believes that such a leap is not possible across the gap, that a man cannot write of a woman's soul, or a white man of a black man, needs to reconsider how he views others"
Knowing something doesn't have to mean experiencing it firsthand, but I do think it makes a difference. I mean, I could read up on life in Iran and then write a story set in Tehran, but there's all kinds of little details I just wouldn't get without either asking a person who'd lived there or going there myself. (To take an example I do know, it's common for Greek farmers at the market to give you extra food instead of change. Cause they seriously hate doing it, I don't know the reasoning but if I read something where someone always got change from the farmers--unlikely but possible--I'd be like pssh yeah right. Also 'The Long Earth' honestly doesn't get Madison right.)
Mailer knows what he's talking about. All writers, even the ones that claim to 'write what they know,' end up writing about things they haven't personally experienced at one point or another. It's just that some can pull off more invention than others.