Instabilities in thin elastic sheets, such as wrinkles, are of broad interest both from a fundamental viewpoint and also because of their potential for engineering applications. Nematic liquid crystal elastomers offer a new form of control of these instabilities through direct coupling between microscopic degrees of freedom, resulting from orientational ordering of rod-like molecules, and macroscopic strain. By a standard method of dimensional reduction, we construct a plate theory for thin sheets of nematic elastomer. We then apply this theory to the study of the formation of wrinkles due to compression of a thin sheet of nematic liquid crystal elastomer atop an elastic or fluid substrate. We find the scaling of the wrinkle wavelength in terms of material parameters and the applied compression. The wavelength of the wrinkles is found to be non-monotonic in the compressive strain owing to the presence of the nematic. Finally, due to soft modes, the critical stress for the appearance of wrinkles can be much higher than in an isotropic elastomer and depends nontrivially on the manner in which the elastomer was prepared.