When Jews were baptized in the 1st cent BCE and the ist century CE
were men and women baptized separately?

For Jewish ritual baths (a mikvah) the sexes have always been strictly separated. 

This opens up the question of just what John the Baptist taught/practiced.

I completely agree with Waukon's answer, but would also add (with
reference to John the Baptist) that what he practiced and taught can't
fully be known as fact.  It should also be clarified that the use of
the Mikvah is still widely practiced.