The transition to turbulence via spatiotemporal intermittency is investigated in the context of coupled maps defined on small-world networks. The local dynamics is given by the Chaté-Manneville minimal map previously used in studies of spatiotemporal intermittency in ordered lattice. The critical boundary separating laminar and turbulent regimes is calculated on the parameter space of the system, given by the coupling strength and the rewiring probability of the network. Windows of relaminarization are present in some regions of the parameter space. New features arise in small-world networks; for instance, the character of the transition to turbulence changes from second-order to a first-order phase transition at some critical value of the rewiring probability. A linear relation characterizing the change in the order of the phase transition is found. The global quantity used as order parameter for the transition also exhibits nontrivial collective behavior for some values of the parameters. These models may describe several processes occurring in nonuniform media where the degree of disorder can be continuously varied through a parameter.