Recently a physical medium was fabricated in which both the effective permittivity $\epsilon(ømega)$ and the effective permeability $\mu(ømega)$ are simultaneously negative over a restricted frequency range. Thus, in this frequency range, such a medium is left-handed, and is characterized by a negative refractive index. A left-handed medium should exhibit unusual phenomena associated with the propagation and scattering of electromagnetic waves. In our paper we study the scattering of p- and s-polarized electromagnetic waves from a weakly rough one-dimensional random surface of a left-handed medium. We assume that the surface profile function is a single-valued function of the coordinate in the mean plane of the surface that is normal to its grooves and ridges, and constitutes a zero-mean, stationary, Gaussian random process. We show that in contrast to nonmagnetic media with a negative dielectric function, the planar surface of a left-handed medium can support both p- and s-polarized surface electromagnetic waves. The reflectivity of such a surface as a function of the angle of incidence displays structure associated with the existence of a Brewster angle in both polarizations and the existence of a critical angle for total internal reflection in both polarizations. The angular distribution of the intensity of the light that has been scattered incoherently displays an enhanced backscattering peak, and Yoneda bands, for both polarizations of the incident light.