We study the coverage dependence of surface diffusion coefficients for a strongly interacting adsorption system O/W(110) via Monte Carlo simulations of a lattice-gas model. In particular, we consider the nature and emergence of memory effects as contained in the corresponding correlation factors in tracer and collective diffusion. We show that memory effects can be very pronounced deep inside the ordered phases and in regions close to first and second order phase transition boundaries. Particular attention is paid to the details of the time dependence of memory effects. The memory effect in tracer diffusion is found to decay following a power law after an initial transient period. This behavior persists until the hydrodynamic regime is reached, after which the memory effect decays exponentially. The time required to reach the hydrodynamical regime and the related exponential decay is strongly influenced by both the critical effects related to long-wavelength fluctuations and the local order in the overlayer. We also analyze the influence of the memory effects on the effective diffusion barriers extracted from the Arrhenius analysis. For tracer diffusion, we find that the contribution from memory effects can be as large as 50% to the total barrier. For collective diffusion, the role of memory effects is in general less pronounced.