4-Color Theorem on Surfaces Is it true, that the minimum number of colors to color a map is still 4, even if the surface you draw the map upon is more complex than a sphere?
What if we have “Planar” graphs on Möbius strips or on a torus ?
 A: Though others have already given more ambitious answers, it may yet be worthwhile to explain why "pure thought" shows that the answer to the OP's question in the first paragraph must be no.
The key observation is this: every finite graph can be embedded in some subsurface of $\mathbb{R}^3$.  To do this, start with a 2:1 planar immersion of the graph, i.e., a map which is locally an embedding into the plane at globally has, at worst, two edges crossing at any given point.  (It is an easy exercise to prove that such things exist for any finite graph.)  Now imagine the graph is the blueprint for a highway: it will be a bad idea for the highway to have self-intersections, so what do we do?  Well, as in the real world, whenever the highway would cross itself, we can build an overpass, lifting one branch up into the third dimension so that it does not cross the other.  In topological terms, we add a handle to the plane in which the graph is embedded.  Thus we succeed in embedding the graph in a surface, which is in fact the $g$-handled torus (where $g$ is the number of planar crossings) minus a single point (because we are starting with the plane rather than the $2$-sphere).  
[This argument actually proves something quantitative: we define the crossing number of a finite graph to be the minimal number of crossings in any $2:1$ planar immersion, and we define the embedding genus of a finite graph to be the minimum genus of a compact surface into which $G$ embeds (thus planar graphs are precisely those of genus zero).  Then the above argument shows that the embedding genus of $G$ is less than or equal to the crossing number of $G$.]
For any $n \in \mathbb{Z}^+$, the complete graph $K_n$ has chromatic number $n$.  Thus the map coloring numbers of a compact orientable surface of genus $g$ must tend to infinity with $g$.  (The precise formula is given in Qiaochu's answer.)  In fact, in the same 1968 paper in which they proved Heawood's Conjecture, Ringel and Youngs gave a precise formula for the embedding genus of $K_n$: for $n \geq 3$ it is $\frac{(n-3)(n-4)}{12}$.  (Clearly it is $0$ for $1 \leq n \leq 4$.)
Comments:
1) I say "embedding genus" where most graph theorists say "genus".  As an arithmetic geometer who encounters graphs while studying degeneration of algebraic curves, I reserve the term "genus" of a graph for what is classically called the cyclomatic number, i.e., the first Betti number of the corresponding cell complex.
2) I know less about this subject than the above answer might indicate.  For instance, I found the computation of the embedding genus of $K_n$ via an internet search while writing this answer.  In particular I have not read the paper of Ringel and Youngs.  Anyone who wishes to add further information on this subject will be educating me first of all...
A: Apparently, that code for 7-coloring a torus from Wagon's book that I was speaking of in the comments is a bit old; here's an update for newer versions of Mathematica:
spiral[theta0_, theta1_, phi0_, phi1_, color_] := 
 ParametricPlot3D[{
  (4 + Cos[1/143 (144 phi + 12 theta)]) Cos[1/143 (12 phi + 144 theta)],
  (4 + Cos[1/143 (144 phi + 12 theta)]) Sin[1/143 (12 phi + 144 theta)], 
   Sin[1/143 (144 phi + 12 theta)]},
     {theta, theta0, theta1}, {phi, phi0, phi1},
  Mesh -> False, PlotStyle -> color]

Show[
     spiral[Pi/12, (21*Pi)/12, Pi/3, 2*Pi, White],
     spiral[-((3*Pi)/12), -(Pi/12), Pi/2, (13*Pi)/6, Green],
     spiral[-(Pi/12), Pi/12, Pi/3, 2*Pi, Brown],
     spiral[-(Pi/6), 0, Pi/6, Pi/3, Yellow],
     spiral[Pi/6, (23*Pi)/12, Pi/6, Pi/3, Blue],
     spiral[0, Pi/6, Pi/6, Pi/3, Purple], 
     spiral[Pi/12, (11*Pi)/6, 0, Pi/6, Red],
   Axes -> None, Boxed -> False, Lighting -> "Neutral", 
   PlotRange -> All, ViewPoint -> {2, 0.2, 1.2}]


A: Thanks for updating my code. I have left this torus example out of the newest edition of my book. 
Slightly related: Mathematica has a database (GraphData) of 6000+ graphs. I have just gone through ALL the planar ones in that database and determined the chromatic number (typically 3 or 4). In particular I did all the polyhedra skeletons and their duals, motivated by a (Trubridge) light fixture I purchased. The main algorithm is Kempe's method, described in detail in my book (Mathematica in Action). Using ILP (integer-linear programming) is also possible on modest sized graphs to determine chromatic numbers, or edge chromatic numbers, etc. I don't know if there is anything especially interesting about the polyhedral case: among the 1100 chromatic numbers I found for such "polyhedral graphs", about 100 were 4 and 1100 were 3. For more info on any of this, contact me. 
For named polyhedron graphs only the following were 4-chromatic:
"IcosahedralGraph", "PentakisDodecahedralGraph", "SmallTriakisOctahedralGraph", "SnubDodecahedralGraph", "TetrahedralGraph", "TriakisIcosahedralGraph", "TriakisTetrahedralGraph".
As for relevance to the original question, I can say that my Kempe implementation is pretty fast for planar graphs, having succeeded on the graph of all 3300 counties in the US. As for the famous counterexamples, I conjecture that one can always get around them with Kempe by simply permuting the vertices and trying again if one reaches an impasse.
Stan Wagon  (wagon  a t   macalester  d o t   e d u )
A: No. The correct replacement for $4$ for all compact surfaces without boundary except the Klein bottle is given by the Ringel-Youngs theorem (formerly the Heawood conjecture): it takes 
$$\left\lfloor \frac{7 + \sqrt{49 - 24 \chi}}{2} \right\rfloor$$
colors except for the Klein bottle where it takes $6$, where $\chi$ is the Euler characteristic of the surface. For the torus, $\chi = 0$, so it takes $7$ colors. I don't know the answer off the top of my head for a Möbius strip. 
