We apply a square-gradient density functional theory to study the nucleation of the gas-to-liquid transition for nonideal binary mixtures. For weakly nonideal mixtures, we predict deviations from ideal behavior in the compositions and free energies of critical nuclei. When the nonideality becomes large enough to allow miscibility gaps, some qualitatively new features arise. We find regions in phase space in which more than one critical nucleus can form, as well as cases in which the critical nucleus itself begins to phase separate, forming a structure of cylindrical symmetry in which the two ends are enriched in the two components of the mixture.