The adsorption of carboxymethylcellulose (CMC), and the subsequent effect on bubble-surface interactions, has been studied for a graphite surface. CMC adsorbs on highly oriented pyrolytic graphite (HOPG) in specific patterns: when adsorbed from a solution of low concentration it forms stretched, isolated and sparsely distributed chains, while upon adsorption from a solution of higher concentration, it forms an interconnected network of multilayer features. The amount and topography of the adsorbed CMC affect the electrical properties as well as the wettability of the polymer-modified HOPG surface. Adsorption of CMC onto the HOPG surface causes the zeta potential to be more negative and the modified surface becomes more hydrophilic. This increase in both the absolute value of zeta potential and the surface hydrophilicity originates from the carboxymethyl groups of the CMC polymer. The effect of the adsorbed polymer layer on wetting film drainage and bubble-surface/particle attachment was determined using high speed video microscopy to monitor single bubble-surface collision, and single bubble Hallimond tube flotation experiments. The time of wetting film drainage and the time of three-phase contact line spreading gets significantly longer for polymer-modified HOPG surfaces, indicating that the film rupture and three-phase contact line expansion were inhibited by the presence of polymer. The effect of longer drainage times and slower dewetting correlated with reduced flotation recovery. The molecular kinetic (MK) model was used to quantify the effect of the polymer on dewetting dynamics, and showed an increase in the jump frequency for the polymer adsorbed at the higher concentration.