How do I know this? Well you know there is a man and a woman. You also know that at least one of them is lying.
That means that if the one with black hair is a lier than it's a woman, but that would mean the red haired one is a man.
What if the red-haired one was lying, that means that he's a man, which means that the other one must be a woman.
In both cases, the one with black hair is the woman.
Which means they're both lying.