The formalism for the Dirac-Brueckner approach to the nuclear many-body problem is described including its basis in relativistic two-nucleon scattering. A family of relativistic meson-exchange potentials is constructed which (apart from the usual coupling terms for heavy mesons) apply the pseudovector (gradient) coupling for the interaction of pseudoscalar mesons (\ensuremath{\pi},\ensuremath{\eta}) with nucleons. These potentials describe low-energy two-nucleon scattering and the deuteron data accurately. Using these potentials, the properties of nuclear matter are calculated in the Dirac-Brueckner-Hartree-Fock approximation, in which the empirical nuclear matter saturation is explained quantitatively. The effective two-body interaction in the nuclear matter medium (G matrix) is calculated directly in the nuclear matter rest frame. Thus, cumbersome transformations between the two-nucleon center-of-mass frame and the nuclear matter rest frame are avoided. Size and nature of relativistic effects included in the present approach are examined in detail. The formalism, the potentials, and the results of this paper may also serve as a basis and a realistic starting point for systematic relativistic nuclear structure studies as well as for the investigation of further relativistic many-body corrections and of contributions of higher order.