Take the proof that any compact smooth manifold admits triangulations, and set the dimension to two. 

The idea goes like this:

* Embed your surface (or $n$-manifold) in $\mathbb R^5$ ($\mathbb R^{2n+1}$ in general).  

* Triangulate $\mathbb R^5$, and make the surface transverse to the triangulation.  If the surface does not intersect each simplex in a locally linear manner, subdivide the triangulation and repeat this step until it does. 

* The pull-back of the triangulation to the surface is a decomposition into convex polyhedra.   A subdivision turns this into a triangulation.