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 follows an inverse logarithmic law. As the system approaches its final state, a growing number of beads have to be rearranged to enable a local density increase. A free volume argument shows that this number grows as N = ρ/(1 - ρ). The time scale associated with such events increases exponentially e N , and as a result a logarithmically slow approach to the final state is found ρ ~ - ρ(t) 1/ln t. Furthermore, a one-dimensional toy model that captures this relaxation dynamics as well as the observed density fluctuations is discussed.