Znamy obu męzczyzn. . We know both men. We know Adam and Marek
Obie znamy mężczyzn - We both (Ania i Kasia) know men
Obaj znamy mężczyzn- We both (Adam i Marek) know men
Oboje znamy mężczyzn - We both (Kasia i Marek) know men
I think those three at first interpretation are about "we know how men are like".
The word "obu" is accusative of the male-personal (m1) numeral "obaj" (meaning two of two available). It is a bit special one, because there is none similar for other quantities ("three of three available" etc.), but it works similar to collective numerals. It means that the noun following the numeral takes the same case as numeral, in plural. And "mężczyzn" is right accusative plural of "mężczyzna"
For a simple explanation about usage of polish numerals you may take a look at wikipedia article you may also like to take a look into Polish Grammar in a Nutshell starting from page 39, or to an in-depth study here