Obstructions for embedding a graph on a surface of genus g Kuratowski's theorem tells us the complete graph $K_5$ and the bipartite graph $K_{3,3}$ are the only obstructions to a graph being planar, ie embeddable in the plane with no edge-crossings.

Is the list of obstructions to being able to embed a graph with no edge-crossings on the surface of genus $g$ known to be finite for all $g$?

 A: For the projective plane, i.e. the nonorientable surface of genus 1, this is known. Look at "A Kuratowski Theorem for the Projective Plane" in the homepage of Dan Archdeacon here:
http://www.emba.uvm.edu/~archdeac/
This was his PhD thesis. In particular, he found that there are exactly 103 graphs such that if any graph $G$ contains one of these graphs as a subgraph, then $G$ cannot be not embedded into projective plane. You can refer to his original thesis for the list of the 103 graphs, or you can refer to the Appendix A of the book "Graphs on Surfaces" by Bojan Mohar and Carsten Thomassen.
A: I'll just remark that the fact that every surface has a finite number of excluded minors (and also topological minors) does not require the full strength of the Graph Minors Theorem.  Indeed, the proof relies on the following three facts:


*

*The Grid Theorem.  There exists a function $f: \mathbb{N} \to \mathbb{N}$, such that every graph with tree-width at least $f(n)$, contains the $n \times n$ grid as a minor.

*Graphs of bounded tree-width are well-quasi-ordered.  For any $k$, the class of graphs of tree-width at most $k$ is well-quasi-ordered.

*Forbidden minors for surfaces do not contain arbitrarily large grid minors.  There is a function $h: \mathbb{N} \to \mathbb{N}$, such that every minor-minimal graph not embeddable on a surface of genus $g$ does not contain an $h(g) \times h(g)$ grid as a minor.  
All three of these facts now have very compact proofs.  In fact, proofs for (1) and (3), and a sketch of a proof of (2) can be found in Diestel's Graph Theory textbook.  See here to peruse the book online.  
A: Yes. Wagner's Conjecture/Robertson and Seymour's Theorem says that any graph family closed under taking minors can be defined by specifying a finite list of forbidden minors. For any surface $S$, the graphs embeddable $S$ without crossing edges forms a family closed under taking minors. 
I haven't looked carefully at it but Jim Belk's introduction to graph minor theory seems good. On the linked page he mentions the following facts: the projective plane has 35 forbidden minors, the number for the torus is in the hundreds thousands (at least, the precise number/collection is not known), and in general the number of forbidden minors grows exponentially with the genus. 
