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.