We report on very soft X-ray sources (VSSs) in M31. In a survey which was most sensitive to soft sources in four 8'x8' regions covered by Chandra's ACIS-S S3 CCD, we find 33 VSSs that appear to belong to M31. Fifteen VSSs have spectral characteristics mirroring the supersoft X-ray sources studied in the Magellanic Cloud and Milky Way ($k T_{eff} \leq 100$ eV); we therefore call these ``classical'' supersoft sources, or simply supersoft sources (SSSs). Eighteen VSSs may either have small (< 10%) hard components, or slightly higher effective temperatures (but still < 350 eV). We refer to these VSSs as quasisoft sources (QSSs). While hot white dwarf models may apply to SSSs, the effective temperatures of QSSs are too high, unless, e.g., the radiation emanates from only a small portion of surface. Two of the SSSs were first detected and identified as such through ROSAT observations. One SSS and one QSS may be identified with symbiotics, and 2 SSSs with supernova remnants. Both SSSs and QSSs in the disk are found near star-forming regions, possibly indicating that they are young. VSSs in the outer disk and halo are likely to be old systems; in these regions, there are more QSSs than SSSs, which is opposite to what is found in fields closer to the galaxy center. The largest density of bright VSSs is in the bulge; some of the bulge sources are close enough to the nucleus to be remnants of the tidal disruption of a giant by the massive central black hole. By using Chandra data in combination with ROSAT and XMM observations, we find most VSSs to be highly variable, fading from or brightening toward detectability on time scales of months. There is evidence for VSSs with low luminosities ($\sim 10^{36}$ erg s$^{-1}$).