working in hyperbolic geometry I wonder if anyone can provide me with a simple step-by-step proof in hyperbolic geometry of a fact that does not hold in Euclidean geometry.
I imagine an answer to be a series of statements, such that later statements follow from earlier ones. It is not strictly necessary to get back to axioms, so it is possible to use some theorems that are not justified.
Also, I am not looking for a proof of the fact that some tiling is possible in hyperbolic plane. (Which is not to say these are not interesting.)
 A: Regular hyperbolic tilings exist in H2, H3, and H4, and with points on the horizon as far as H9.  There are an infinite number of archimedean tilings, but even more quasi-regular tilings.
A very famous tiling is the 'Not Knot' poster, which shows a very detailed projection of the right-angled dodecahedron, tiling H3 space.
A good deal of work has been done towards devising a concise notation that exactly covers these things, but it needs more work, because there be supprises in there.
For example, any {p,q} exists (p-gons, q at a corner), for all p,q where 1/2+1/p+1/q < 1.  Coxeter wrote a paper on the subject in '12 Essays' (the beauty of mathematics).  Melinda Green wrote a java applet 'tyler' which allows one to construct any tiling given a vertex figure.  
A: My favourite example of a surprising fact in hyperbolic geometry is the following:

Every triangle in the hyperbolic plane $\mathbb{H}$ has area less than or equal to $\pi$. Further, any ideal triangle (a triangle with vertices on the boundary $\partial\mathbb{H}$) has area equal to $\pi$.

This is an immediate consequence of the Gauss-Bonnet theorem which, in the hyperbolic case, can be proved without needing the full machinery of differential geometry.
For general Riemannian manifolds, the Guass-Bonnet theorem says:

General Gauss-Bonnet. Let $M$ be a compact $2$-dimensional Riemannian manifold with boundary $\partial M$ and let $K$ be the Gaussian curvature of $M$ and $k_g$ be the geodesic curvature of $\partial M$. Then $$\int_M K\, dA+\int_{\partial M} k_g\, ds=2\pi\chi(M)$$ where $dA$ is an area element, $ds$ is a line element on the boundary, and $\chi(M)$ is the Euler characteristic of $M$.

In the hyperbolic case for triangles, this reduces to:

Hyperbolic Gauss-Bonnet for triangles. Let $\Delta$ be a hyperbolic triangle with internal angles $\alpha,\beta,\gamma$. Then $$\mbox{Area}_{\mathbb{H}}(\Delta)=\pi-(\alpha+\beta+\gamma).$$

The remarkable implication of this theorem is that the area of a hyperbolic triangle is fully determined by its angles (in stark contrast to the case of triangles in Euclidean space) and that, because angles are non-negative (they can be zero if vertices are on the boundary), then we see that $\pi$ is an upper limit for the area of any triangle in $\mathbb{H}$ (also in stark contrast to the case of triangles in Euclidean space). This bound is then tight, and attained by any triangle with all three vertices on the boundary of $\mathbb{H}$ which means $\alpha+\beta+\gamma=0+0+0$.
This is surprising mostly because the area of the entire hyperbolic plane is unbounded and so, unlike the sphere for example, we might expect that triangles can be formed with arbitrarily large area by simply pushing vertices further and further away from each other. The Gauss-Bonnet theorem though says that this is not the case, and in fact pushing vertices away from each other has less and less effect the more they are moved, even infinitely far away from each other.
Of course, any convex hyperbolic polygon can be partitioned into a minimal number of triangles, and so this also gives bounds on the area of such polygons (can you see what the bound would be for a polygon with $E$ edges and internal angles $\gamma_1,\ldots\gamma_{E}$?)
For a well written proof of the Gauss-Bonnet theorem for hyperbolic triangles which does not rely on the general theorem (it uses nothing more than basic double integration and the theory of Mobius transformations) I would recommend the following page of lecture notes provided on Charles Walkden's webpage.
A: Here's a sample theorem, then, which astonished me when I first realized it. I'll do the hyperbolic argument and leave the spherical case to you.

THEOREM: Given two triangles $\triangle ABC$ and $\triangle A'B'C'$ in the hyperbolic plane. If $\angle A = \angle A'$, $\angle B = \angle B'$, and $\angle C = \angle C'$, then $\triangle ABC\cong\triangle A'B'C'$.

By an isometry, we can move $A'$ to $A$ and then rotate so that $\overline{A'B'}$ is contained in $\overrightarrow{AB}$. Then $\overline{A'C'}$ will be contained in $\overrightarrow{AC}$, as well. 
Case (i): If $B'=B$, then either $\triangle A'B'C'\subset\triangle ABC$ (here I mean that the interior of the first triangle is contained in the interior of the second) or $\triangle A'B'C'\supset\triangle ABC$. Recall that the area of a triangle with interior angles $\iota_1$, $\iota_2$, $\iota_3$ is $\pi-(\iota_1+\iota_2+\iota_3)$. Thus, $\triangle A'B'C'$ and $\triangle ABC$ have the same area, so we must have $\triangle ABC = \triangle A'B'C'$, so $C'=C$ and the triangles are congruent. 
Case (ii): Area considerations will next show that if $B'$ is between $A$ and $B$, then  $C'$ cannot be between $A$ and $C$ (inclusive). 
Case (iii): If $B'$ is between $A$ and $B$ and $C'$ is past $C$, then $\overline{BC}$ and $\overline{B'C'}$ intersect, say, at $D$. [The reader should, of course, draw a picture at this stage.] Since $\angle ABC = \angle A'B'C'$ and $\angle ACB = \angle A'C'B'$, the angles of each of $\triangle B'DB$ and $\triangle CDC'$ add up to more than $\pi$, which is impossible. So this case, too, cannot occur. 
The remaining cases when $B'$ is past $B$ are identical to those we've already considered. Thus, we're left only with the one possibility: $\triangle ABC \cong \triangle A'B'C'$.
