The idea that surface effects may play an important role in suppressing $e_g$ Fermi surface pockets on Na$_x$CoO$_2$ $(0.333 le x le 0.75)$ has been frequently proposed to explain the discrepancy between LDA calculations (performed on the bulk compound) which find $e_g$ hole pockets present and ARPES experiments, which do not observe the hole pockets. Since ARPES is a surface sensitive technique it is important to investigate the effects that surface formation will have on the electronic structure of Na$_{1/3}$CoO$_2$ in order to more accurately compare theory and experiment. We have calculated the band structure and Fermi surface of cleaved Na$_{1/3}$CoO$_2$ and determined that the surface non-trivially affects the fermiology in comparison to the bulk. Additionally, we examine the likelihood of possible hydroxyl cotamination and surface termination. Our results show that a combination of surface formation and contamination effects could resolve the ongoing controversy between ARPES experiments and theory.