Bubble-propelled catalytic colloids stand out as a uniquely efficient design for artificial controllable micromachines, but so far lack a general theoretical framework that explains the physics of their propulsion. Here we develop a combined diffusive and hydrodynamic theory of bubble growth near a spherical catalytic colloid, that allows us to explain the underlying mechanism and the influence of environmental and material parameters. We identify two dimensionless groups, related to colloidal activity and the background fluid, that govern a saddle-node bifurcation of the bubble growth dynamics, and calculate the generated flows analytically for both slip and no slip boundary conditions on the bubble. We finish with a discussion of the assumptions and predictions of our model in the context of existing experimental results, and conclude that some of the observed behaviour, notably the ratchet-like gait, may stem from peculiarities of the experimental setup rather than fundamental physics of the propulsive mechanism.