Recent ROSAT surveys suggest that galaxies can constitute the new class of faint sources required to explain the full phenomenology of the cosmic X-ray background (XRB). To test this hypothesis without resorting to optical identifications, we compute the two-point cross-correlation function (CCF) estimator W-xg(theta) between 62 Einstein IPC fields (0.81-3.5 keV) and the APM Northern Galaxy Catalog (13.5 < E < 19.0). At zero lag (theta = 0), we detect a 3.5 sigma correlation signal with an amplitude of W-xg(0) = 0.045 +/- 0.013. This signal passes a series of control tests. At non-zero lag (theta > 0), the angular dependence of W-xg has two main features: the main signal for theta less than or similar to 4', and an almost flat plateau with an amplitude of W-xg(theta greater than or similar to 4') similar or equal to 0.015. When fields with galaxy clusters as Einstein targets are removed, the plateau virtually disappears, and the zero-lag amplitude becomes W-xg(0) = 0.029 +/- 0.013. We develop a simple, two-dimensional formalism to interpret the CCF that takes into account the point-spread function of the imaging X-ray detector. Three distinct effects can produce a correlation signal: the X-ray emission from galaxies themselves, the clustering of galaxies with discrete X-ray sources, and the clustering of galaxies with diffuse X-ray emission. It is likely that the plateau at large angles is due to the last effect through the residual diffuse X-ray emission from clusters of galaxies. We do not detect any significant clustering between discrete X-ray sources and galaxies. Using only the fields with noncluster targets, we find that the mean X-ray intensity of APM galaxies in the 0.81-3.5 keV band is (2.2 +/- 1.1) x 10(-6) counts s(-1) arcmin(-2), corresponding to 1.5% +/- 0.8% of the XRB intensity. The mean X-ray flux of galaxies with [E] = 17.5 +/- 0.3 is then (8.1 +/- 4.7) x 10(-16) ergs s(-1) cm(-2). This agrees within 1 sigma with the X-ray flux expected from earlier direct studies of brighter, nearby galaxies, which were shown to result in a total integrated galaxy contribution to the XRB of about 13%. We discuss how this powerful cross-correlation method can be used to measure the flux of X-ray sources well below the detection limit of X-ray instruments and, perhaps, to probe otherwise undetectable faint diffuse X-ray emission.