Upon entering the main building of the Khans' camp and talking to Garl Death-Hand, the leader of the Khans, the Vault Dweller must tell him that they want to join, and "kick some serious ass" (choosing any other dialogue option will only provoke hostility with the Khans). Garl will then proceed to tell the Dweller that he is tired of his female slaves, and that they must prove themself by killing said slaves.
Doing so is easy, as they will not attack back and instead run away. However, they must be killed without any or either of them leaving the camp, as the Khans will be upset if that happens. Once both are dead, Garl will name the Vault Dweller a "friend of the Khans" and grant them free access to the camp.