The slow nucleation of clathrate hydrates is a central challenge for their use in the storage and transportation of natural gas. Molecules that strongly adsorb to the clathrate-water interface decrease the crystal-water surface tension, lowering the barrier for clathrate nucleation. Surfactants are widely used to promote the nucleation and growth of clathrate hydrates. It has been proposed that these amphiphilic molecules bind to the clathrate surface via hydrogen bonding. However, recent studies reveal that PVCap, an amphiphilic polymer, binds to clathrates through hydrophobic moieties. Here we use molecular dynamic simulations and theory to investigate the mode and strength of binding of surfactants to the clathrate-water interface and their effect on the nucleation rate. We find that the surfactants bind to the clathrate-water interface exclusively through their hydrophobic tails. The binding is strong, driven by the entropy of dehydration of the alkyl chain, as it penetrates empty cavities at the hydrate surface. The hydrophobic attraction of alkyl groups to the clathrate surface also results in strong adsorption of alkanes. We identify two regimes for the binding of surfactants as a function of their density at the hydrate surface, which we interpret to correspond to the two steps of the Langmuir adsorption isotherm observed in experiments. Our results indicate that hydrophobic attraction to the clathrate-water interface is key for the design of soluble additives that promote the nucleation of hydrates. We use the calculated adsorption coefficients to estimate the concentration of sodium dodecyl sulfate (SDS) required to reach nucleation rates for methane hydrate consistent with those measured in experiments. To our knowledge, this study is the first to quantify the effect of surfactant concentration in the nucleation rate of clathrate hydrates.