A quantitative understanding of organism-level behavior requires predictive models that can capture the richness of behavioral phenotypes, yet are simple enough to connect with underlying mechanistic processes. Here we investigate the motile behavior of nematodes at the level of their translational motion on surfaces driven by undulatory propulsion. We broadly sample the nematode behavioral repertoire by measuring motile trajectories of the canonical lab strain $C. elegans$ N2 as well as wild strains and distant species. We focus on trajectory dynamics over timescales spanning the transition from ballistic (straight) to diffusive (random) movement and find that salient features of the motility statistics are captured by a random walk model with independent dynamics in the speed, bearing and reversal events. We show that the model parameters vary among species in a correlated, low-dimensional manner suggestive of a common mode of behavioral control and a trade-off between exploration and exploitation. The distribution of phenotypes along this primary mode of variation reveals that not only the mean but also the variance varies considerably across strains, suggesting that these nematode lineages employ contrasting ``bet-hedging'' strategies for foraging.