The pervasive Mars dust is continually transported between the surface and the atmosphere. When on the surface, dust increases the albedo of darker underlying rocks and regolith, which modifies climate energy balance and must be quantified. Remote observation of surface albedo absolute value and albedo change is however complicated by dust itself when lifted in the atmosphere. Here we present a method to calculate and map the bolometric solar hemispherical albedo of the Martian surface using the 2004 - 2010 OMEGA imaging spectrometer dataset. This method takes into account aerosols radiative transfer, surface photometry, and instrumental issues such as registration differences between visible and near-IR detectors. Resulting albedos are on average 17% higher than previous estimates for bright surfaces while similar for dark surfaces. We observed that surface albedo changes occur mostly during the storm season due to isolated events. The main variations are observed during the 2007 global dust storm and during the following year. A wide variety of change timings are detected such as dust deposited and then cleaned over a Martian year, areas modified only during successive global dust storms, and perennial changes over decades. Both similarities and differences with previous global dust storms are observed. While an optically thin layer of bright dust is involved in most changes, this coating turns out to be sufficient to mask underlying mineralogical near-IR spectral signatures. Overall, changes result from apparently erratic events; however, a cyclic evolution emerges for some (but not all) areas over long timescales.