It is known that every surface can be represented by a polygon and glueing the sides appropriately (A source). It is also known that the only tessellations of the plane are by squares, triangles and hexagons. It is for example possible to "tessellate" the plane by the torus 
or by the Klein bottle 
. But is it possible for an arbitrary surface? My guess would be that it is not.
EDIT: I have since found the chapter "Plane tessellation representations of compact surfaces" in "Surface Topology", which explains why it is possible to "tessellate" the hyperbolic plane with the fundamental polygon of surfaces.
No, this is not possible for any surface, and the only surfaces you can do this are the torus and the Klein bottle.
So suppose $P$ is some polygon in the plane such that with some gluing data of its edges we obtain a tessellation of the plane, and considering the quotient space we get a surface $S$.
Say the vertices of $P$ are identified to $v$ points of the quotient space $S$. Each edge of $P$ is glued to only one other edge; as $S$ is a closed manifold. Thus $P$ has an even number $2n$ of edges, which become $n$ arcs in the quotient $S$.
Recall that for any surface $X$ obtained by gluing $p$ disjoint polygons of the plane along their edges, the Euler characteristic $\chi(X)$ of $X$ equals
$$ p-n+v$$
where $2n$ is the number of edges of the polygons; this number is even because the same reason given above, and $v$ is the number of points of $X$ coming from a vertex of one of the polygons. The fact that $\chi(X)$ does not depend on this particular description of the surface $X$ using polygons is proved using the homology groups of $X$, a proof of this can be found for instance in Bredon's book Topology and Geometry.
So for our surface $S$ we get its Euler characteristic is $1-n+v$. Now as with $P$ and this gluing data we get a tessellation of the plane, if $\{v_1,\cdots,v_n\}$ is the equivalence class of a vertex of $P$ in the quotient; of course the $v_i$'s are vertices of $P$, then we must have $$\sum_{i=1}^{n}\theta_i=2\pi,$$
where $\theta_i$ is the angle of $P$ at the vertex $v_i$, hence the sum of the internal angles of $P$ must sum up to $2\pi v.$
However as $P$ has $2n$ sides, the sum of its interior angles must be $(2n-2)\pi$, in consequence $$2\pi\chi(S)=2\pi(1-n+v)=\pi(2-2n)+2\pi v=0.$$
Therefore the Euler characteristic of $S$ must be $0$, and thus $S$ can only be either the torus or the Klein bottle.
The equality $2\pi\chi(S)=0$ we obtained is actually a very particular case of the Gauss-Bonnet theorem.