2 added 755 characters in body

Addendum in the Riemannian setting: Everything works fine if your manifold is compact. But if it is noncompact, the above definition of a fundamental domain is unsatisfactory. The key reason is that it could happen (even in the hyperbolic case) that if you take the Riemannian metric on $P$ which is the restriction of the metric on $X$ and project it down to the quotient space $P/\sim$ (obtained by gluing faces of $P$) then the resulting metric is incomplete (even if the metric on $M$ is). That's not good! So you need some conditions to ensure that the metric on $P/\sim$ is isometric to the one on $M$. Look in Ratcliffe's book for (somewhat painful) details. The bottom line is: If your manifold is compact, you are in luck (good luck otherwise).

1

If you are interested in definition, look in John Ratcliffe's book "Foundations of hyperbolic manifolds." He discussed fundamental domains for hyperbolic manifolds in great detail and most of the discussion goes through in the context of smooth/PL manifolds. In general, there is no "canonical" definition of a fundamental domain for a manifold. Here is one possible definition of a fundamental domain for a compact connected triangulated manifold $M$:

A fundamental domain for $M$ is a compact contractible (or, you can even require $P$ to be PL homeomorphic to a ball if you wish) polyhedron $P$ so that $M$ is obtained by gluing faces of $P$ via PL homeomorphisms.

It is easy to see why such a fundamental domain exists: Let $S$ be the dual graph to the triangulation of (connected) $M$ (vertices of $S$ are facets, i.e., top-dimensional faces, while the edges correspond to codimension 1 faces along which facets meet). Now, choose $T$, a maximal subtree in $S$. Hence, $T$ contains all the vertices of $S$. Then glue all the facets of the triangulation along the faces corresponding to the edges of $T$. The result is a fundamental domain in the above sense. (Here you see the connection to a existence of a triangulation which.)

There is a different (and, actually, more popular) school of thought concerning fundamental domains. Namely, fundamental domains are defined for properly discontinuous group actions on "nice" topological spaces $X$. If you have a manifold $M$ then the natural space $X$ in this context is its universal cover of $M$ and the group $G$ is the fundamental group $\pi_1(M)$ acting by covering transformations. Assuming, again, that everything is triangulated, you define a fundamental domain for the action of $G$ on $X$ as a polyhedron $P\subset X$ so that the following hold:

1. The $G$-orbit of $P$ covers the entire $X$.

2. $gP \cap P$ is contained in the boundary of $P$ for every $g\in G-1$.

(One has to add more conditions if a metric is present, but we do not need them here.)

Note that such $P$'s may not be contractible. For instance, if $M$ is simply-connected then, necessarily, $M=X=P$.

On the other hand, in the context of hyperbolic manifolds $M$ (and, more generally, manifolds of nonpositive sectional curvature) there is a nice and natural class of fundamental domains in $X$, called Dirichlet domains, which are contractible (since they are star-like). They depend on the choice of a base-point in $X$. You can read more on these in Ratcliffe's book.

In most cases, fundamental domains do not provide much insight into topology of $M$ (once you go beyond dimension $2$), so topologists prefer to describe topology of $M$ through other combinatorial means. For instance, in the context of 3-dimensional manifolds Heegaard splittings (and their generalizations) appear to be most useful. Surgery along links in the 3-sphere is another common way to go.