For sexually reproducing animals, selecting optimal mates is essential for maximizing reproductive fitness. Because the nematode C. elegans reproduces mostly by self-fertilization, little is known about its mate-choice behaviors. While several sensory cues have been implicated in males' ability to recognize hermaphrodites, achieving an integrated understanding of the ways males use these cues to assess relevant characteristics of potential mates has proven challenging. Here, we use a choice-based social-interaction assay to explore the ability of C. elegans males to make and optimize mate choices. We find that males use a combination of volatile sex pheromones (VSPs), ascaroside pheromones, surface-bound chemical cues, and other signals to robustly assess a variety of features of potential mates. Specific aspects of mate choice are communicated by distinct signals: the presence of a sperm-depleted, receptive hermaphrodite is likely signaled by VSPs, while developmental stage and sex are redundantly specified by ascaroside pheromones and surface-associated cues. Ascarosides also signal nutritional information, allowing males to choose well-fed over starved mates, while both ascarosides and surface-associated cues cause males to prefer virgin over previously mated hermaphrodites. The male-specificity of these behavioral responses is determined by both male-specific neurons and the male state of sex-shared circuits, and we reveal an unexpected role for the sex-shared ASH sensory neurons in male attraction to endogenously produced hermaphrodite ascarosides. Together, our findings lead to an integrated view of the signaling and behavioral mechanisms by which males use diverse sensory cues to assess multiple features of potential mates and optimize mate choice.