I just ran across this question, and thought I would give a precise version of the proof Ilya suggested. I believe I learned this proof in Richie Miller's topology course, Michigan State University, 1977 or so.
Choose a triangulation of the surface $S$, equipped with the simplicial metric. Choose a maximal one-ended subforest $F$ of the dual 1-skeleton $S^{(1)}$. By a ``one-ended subforest'' I mean a subgraph each of whose components is a one-ended tree. The subforest $F$ contains every dual $0$-cell, that is, the barycenter of every 2-simplex. Also, $F$ contains dual 1-cells crossing certain $1$-simplices. For each component $T$ of $F$ let $U_T$ be the union of the open 2-simplices and open 1-simplices that contain a point of $T$. The metric completion of $U_T$, denoted $\bar U_T$, is a closed disc with one boundary point removed, and so there is a deformation retraction from $\bar U_T$ onto its boundary $\partial \bar U_T$. These deformation retractions piece together to give a deformation retraction from $S$ onto $S - \cup_T U_T$, wnich is a subcomplex of the 1-skeleton.
By the way, the subforest $F \subset S^{(1)}$ can be constructed by an explicit process. Enumerate the dual $0$-cells $v_1,v_2,\ldots \in S^{(1)}$. Construct one-ended subforests $F_1,F_2,\ldots \subset S^{(1)}$ as follows. $F_1$ is any proper ray based at $v_1$. If $v_n \in F_{n-1}$ then $F_n = F_{n-1}$. If $v_n$ is in a finite component $T$ of $S^{(1)} - F_{n-1}$, choose an dual 1-cell $e$ connecting a $0$-cell of $T$ to a point of $F_{n-1}$, and let $F_n = F_{n-1} \cup T \cup e$. If $v_n$ is in an infinite component $T$ of $S^{(1)} - F_{n-1}$, let $F_n$ be the union of $F_{n-1}$ with an infinite ray in $T$. Noticing that the inclusion $F_{n-1} \subset F_n$ is injective on the component set, it follows that the union of the $F_n$ is a one-ended subforest of $S^{(1)}$, and it is maximal because it contains each $v_i$.
I think this proof generalizes to any dimension, to give the theorem that Igor refers to.