Understanding the microscopic mechanism of nucleation of clathrate hydrates is important for their use in hydrogen storage, CO2 sequestration, storage and transport of natural gas, and the prevention of the formation of hydrate plugs in oil and gas pipelines. These applications involve hydrate guests of varied sizes and solubility in water that form different hydrate crystal structures. Nevertheless, molecular studies of the mechanism of nucleation of hydrates have focused on the single class of small hydrophobic guests that stabilize the sI crystal. In this work, we use molecular dynamics simulations with a very efficient coarse-grained model to elucidate the mechanisms of nucleation of clathrate hydrates of four model guests that span a 2 orders of magnitude range in solubility in water and that encompass sizes which stabilize each one a different hydrate structure (sI and sII, with and without occupancy of the dodecahedral cages). We find that the overall mechanism of clathrate nucleation is similar for all guests and involves a first step of formation of blobs, dense clusters of solvent-separated guest molecules that are the birthplace of the clathrate cages. Blobs of hydrophobic guests are rarer and longer-lived than those for soluble guests. For each guest, we find multiple competing channels to form the critical nuclei, filled dodecahedral cages, (5(12)) cages, empty 5(12) cages, and a variety of filled large (5(12)6(n) with n = 2, 3, and 4) clathrate cages. Formation of empty dodecahedra is an important nucleation channel for all but the smallest guest. The empty 5(12) cages are stabilized by the presence of guests from the blob in their first solvation shell. Under conditions of high supercooling, the structure of the critical and subcritical nuclei is mainly determined by the size of the guest and does not reflect the cage composition or ordering of the stable or metastable clathrate crystals.