We present a CCD-based photometric survey covering 870 arcmin^2 in a young stellar cluster around the young multiple star sigma Orionis. Our survey-limiting R, I, and Z magnitudes are 23.2, 21.8, and 21.0, respectively, the completeness being about 2.2 mag brighter. From our color-magnitude diagrams, we have selected 49 faint objects (I=15-21 mag), which smoothly extrapolate the photometric sequence defined by more massive known members. Adopting the currently accepted age interval of 2-10 Myr for the Orion 1b association, in which sigma Orionis is located, and considering recent evolutionary models, our objects may span a mass range from 0.1 down to 0.02 M_solar, well within the substellar regime. Follow-up low-resolution optical spectroscopy (635-920 nm) for eight of our candidates in the magnitude range I=16-19.5 shows that they have spectral types M6-M8.5, consistent with what is expected for true members. Compared with their Pleiades counterparts of similar types, Hα emission is generally stronger, while Na I and K I absorption lines appear weaker, as expected for lower surface gravities and younger ages. In addition, TiO and in particular VO bands appear to be clearly enhanced in our candidate with the latest spectral type, S Ori 45 (M8.5, I=19.5), compared to objects of similar types in older clusters and the field. We have estimated the mass of this candidate at only 0.020-0.040 M_solar hence, it is one of the least massive brown dwarfs yet discovered. We examine the potential role of deuterium as a tracer of both substellar nature and age in very young clusters. The luminosity and mass at which the burning/preservation of deuterium takes place is a sensitive function of age and can therefore provide a determination of the age of a cluster. The sigma Orionis cluster is an excellent site for determining this transition zone empirically; the most massive brown dwarfs identified are expected to have burned their deuterium content, while the lowest mass ones should have preserved it.