The HARPS search for southern extra-solar planets XXXI. The M-dwarf sample

(Abridged) Searching for planets around stars with different masses probes the outcome of planetary formation for different initial conditions. This drives observations of a sample of 102 southern nearby M dwarfs, using a fraction of our guaranteed time on the ESO/HARPS spectrograph (Feb. 11th, 2003 to Apr. 1st 2009). This paper makes available the sample's time series, presents their precision and variability. We apply systematic searches and diagnostics to discriminate whether the observed Doppler shifts are caused by stellar surface inhomogeneities or by the radial pull of orbiting planets. We recover the planetary signals corresponding to 9 planets already announced by our group (Gl176b, Gl581b, c, d & e, Gl674b, Gl433b, Gl 667Cb and c). We present radial velocities that confirm GJ 849 hosts a Jupiter-mass planet, plus a long-term radial-velocity variation. We also present RVs that precise the planetary mass and period of Gl 832b. We detect long-term RV changes for Gl 367, Gl 680 and Gl 880 betraying yet unknown long-period companions. We identify candidate signals in the radial-velocity time series and demonstrate they are most probably caused by stellar surface inhomogeneities. Finally, we derive a first estimate of the occurrence of M-dwarf planets as a function of their minimum mass and orbital period. In particular, we find that giant planets (m sin i = 100-1,000 Mearth) have a low frequency (e.g. f<1% for P=1-10 d and f=0.02^{+0.03}_{-0.01} for P=10-100 d), whereas super-Earths (m sin i = 1-10 Mearth) are likely very abundant (f=0.36^{+0.25}_{-0.10} for P=1-10 d and f=0.35^{+0.45}_{-0.11} for P=10-100 d). We also obtained eta_earth=0.41^{+0.54}_{-0.13}, the frequency of habitable planets orbiting M dwarfs (1