Experimental studies show that the density of a vibrated granular material evolves from a low density initial state into a higher density final steady state. The relaxation towards the final density value follows an inverse logarithmic law. We propose a simple stochastic adsorption-desorption process which captures the essential mechanism underlying this remarkably slow relaxation. As the system approaches its final state, a growing number of beads have to be rearranged to enable a local density increase. In one dimension, this number grows as $N=\rho/(1-\rho)$, and the density increase rate is drastically reduced by a factor $e^{-N}$. Consequently, a logarithmically slow approach to the final state is found $\rho_{\infty}-\rho(t)\cong 1/\ln t$.