Recently Menard et al. detected a subtle but systematic change in the mean color of quasars as a function of their projected separation from foreground galaxies, extending to comoving separations of ~10Mpc/h, which they interpret as a signature of reddening by intergalactic dust. We present theoretical models of this remarkable observation, using SPH cosmological simulations of a (50Mpc/h)^3 volume. Our primary model uses a simulation with galactic winds and assumes that dust traces the intergalactic metals. The predicted galaxy-dust correlation function is similar in form to the galaxy-mass correlation function, and reproducing the MSFR data requires a dust-to-metal mass ratio of 0.24, about half the value in the Galactic ISM. Roughly half of the reddening arises in dust that is more than 100Kpc/h from the nearest massive galaxy. We also examine a simulation with no galactic winds, which predicts a much smaller fraction of intergalactic metals (3% vs. 35%) and therefore requires an unphysical dust-to-metal ratio of 2.18 to reproduce the MSFR data. In both models, the signal is dominated by sightlines with E(g-i)=0.001-0.1. The no-wind simulation can be reconciled with the data if we also allow reddening to arise in galaxies up to several x 10^10 Msun. The wind model predicts a mean visual extinction of A_V ~0.0133 mag out to z=0.5, with a sightline-to-sightline dispersion similar to the mean, which could be significant for future supernova cosmology studies. Reproducing the MSFR results in these simulations requires that a large fraction of ISM dust survive its expulsion from galaxies and its residence in the intergalactic medium. Future observational studies that provide higher precision and measure the dependence on galaxy type and environment will allow detailed tests for models of enriched galactic outflows and the survival of IG dust.