A quantitative understanding of organism-level behaviour requires predictive models that can capture the richness of behavioural phenotypes, yet are simple enough to connect with underlying mechanistic processes. Here, we investigate the motile behaviour of nematodes at the level of their translational motion on surfaces driven by undulatory propulsion. We broadly sample the nematode behavioural repertoire by measuring motile trajectories of the canonical laboratory strain Caenorhabditis elegans N2 as well as wild strains and distant species. We focus on trajectory dynamics over time scales 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 behavioural 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.