CARMENES is a stabilised, high-resolution, double-channel spectrograph at the 3.5m Calar Alto telescope. It is optimally designed for radial-velocity surveys of M dwarfs with potentially habitable Earth-mass planets. We prepare a list of the brightest, single M dwarfs in each spectral subtype observable from the northern hemisphere, from which we will select the best planet-hunting targets for CARMENES. In this first paper on the preparation of our input catalogue, we compiled a large amount of public data and collected low-resolution optical spectroscopy with CAFOS at the 2.2m Calar Alto telescope for 753 stars. We derived accurate spectral types using a dense grid of standard stars, a double least-squares minimisation technique, and 31 spectral indices previously defined by other authors. Additionally, we quantified surface gravity, metallicity, and chromospheric activity for all the stars in our sample. We calculated spectral types for all 753 stars, of which 305 are new and 448 are revised. We measured pseudo-equivalent widths of H{alpha} for all the stars in our sample, concluded that chromospheric activity does not affect spectral typing from our indices, and tabulated 49 stars that had been reported to be young stars in open clusters, moving groups, and stellar associations. Of the 753 stars, two are new subdwarf candidates, three are T Tauri stars, 25 are giants, 44 are K dwarfs, and 679 are M dwarfs. Many of the 261 investigated dwarfs in the range M4.0-8.0 V are among the brightest stars known in their spectral subtype.