Properties of disordered nematic elastomers and gels are theoretically investigated with emphasis on the roles of nonlocal elastic interactions and crosslinking conditions. Networks originally crosslinked in the isotropic phase lose their long-range orientational order by the action of quenched random stresses, which we incorporate into the affine-deformation model of nematic rubber elasticity. We present a detailed picture of mechanical quasi-Goldstone modes, which accounts for an almost completely soft polydomain-monodomain (PM) transition under strain as well as a “four-leaf clover” pattern in depolarized light scattering intensity. Dynamical relaxation of the domain structure is numerically studied using a simple model. The peak wave number of the structure factor obeys a power-law-type slow kinetics and goes to zero in true mechanical equilibrium. The effect of quenched disorder on director fluctuation in the monodomain state is analyzed. The random frozen contribution to the fluctuation amplitude dominates the thermal one, at long wavelengths and near the PM transition threshold. We also study networks obtained by crosslinking polydomain nematic polymer melts. The memory of the initial director configuration acts as correlated and strong quenched disorder, which renders the PM transition nonsoft. The spatial distribution of the elastic free energy is strongly dehomogenized by external strain, in contrast to the case of isotropically crosslinked networks.