It suffices to consider a connected graph. Start from a point, which is the 1-skeleton of a sphere. By induction, consider a connected graph $G$ and an edge $E$, and let $S$ be the surface in which the complementary graph $G \setminus E$ is embedded as the 1-skeleton of a CW structure.

If $E$ disconnects $G$ into two connected subgraphs, $S$ has two components and you can embed $G$ in their connected sum. If $E$ is a loop edge with base vertex $v$, you can extend the embedding $G \setminus E \to S$ to an embedding $G \to S$ by including $E$ into a corner of some 2-cell near $v$. If $E$ is a nonloop edge with end vertices $v,w$, but $E$ does not disconnect, there are two cases. If there is just one 2-cell touching $v,w$ then you can embed $E$ into that two cell, connecting one corner to another and cutting that 2-cell into two 2-cells. If there are two or more 2-cells touching $v,w$, then there exist 2-cells $C \ne D$ touching $v,w$ respectively, and you can take the "self-connected sum" of $S$ by taking the connected sum of $C$ and $D$ to form an annulus, and then extend the embedding of $G$ by embedding $E$ in that annulus, cutting from one boundary of the annulus to the opposite and subdividing that annulus into a 2-cell.