We consider the elastic constants of phases with nonspherical nuclei, so-called pasta phases, predicted to occur in the inner crust of a neutron star. First, we treat perfectly ordered phases and give numerical estimates for lasagna and spaghetti when the pasta elements are spatially uniform; the results are in order-of-magnitude agreement with the numerical simulations of Caplan, Schneider, and Horowitz, [Phys. Rev. Lett. 121, 132701 (2018)]. We then turn to pasta phases without long-range order and calculate upper (Voigt) and lower (Reuss) bounds on the effective shear modulus and find that the lower bound is zero, but the upper bound is nonzero. To obtain better estimates, we then apply the self-consistent formalism and find that this predicts that the shear modulus of the phases without long-range order is zero if the pasta elements are spatially uniform. In numerical simulations, the pasta elements are found to be modulated spatially and we show that this modulation is crucial to obtaining a nonzero elastic moduli for pasta phases without long-range order. In the self-consistent formalism we find that, for lasagna, the effective shear modulus is linear in the elastic constants that do not vanish when the pasta elements are spatially uniform while, for spaghetti, it varies as the square root of these elastic constants. We also consider the behavior of the elastic constant associated with a homologous strain (hydrostatic compression) of the structure of the pasta phases without long-range order.