The flip graph of triangulations A polygon $P_k$ divided by $k-2$ diagonals into triangles is called a polygonal triangulation. These are the vertices of the triangulation graph $\mathcal P_k$. Two vertices are connected by an edge if one triangulation is obtained from another by the diagonal flip, i.e. we take two triangles of the triangulation that share a side, and in their union (where that side is a diagonal), replace that diagonal by the other diagonal. Sleator, Tarjan, and Thurston proved that the diameter of the
triangulation graph ${\mathcal P}_k$ is bounded above by $2k-10$. Hence the problem of finding a shortest path in that graph between two triangulations is in NP. 
 Question 1.  Is it in P? 
 Question 2.  What is known about the complexity of finding the shortest path in the triangulation graph of other surfaces?
 Update.  I have posted a followup question. 
 A: Just to add a little to Joseph's nice answer, for part 1 of your question: although the problem of computing the flip distance in polynomial time is wide open for triangulations of convex polygons, it can be solved in polynomial time for triangulations of certain highly nonconvex point sets (such as the intersection of the integer lattice with a convex set): see my paper "Happy Endings for Flip Graphs", SoCG 2007 and JoCG 2010.
A: I believe your two questions are not directly related. As far as I know, Question 1 is open.
[Edit. I answered the 2nd question under the interpretation that "the triangulation graph of other surfaces" meant the graph of the surface triangulation, which, as Agol pointed out,
is likely not what Mark meant.  Rather he meant the flip graph, which is the focus of the 1st
question.  So the below does not answer the intended question. (The flip graph does not always
make sense on a surface.)]
Let me address Question 2.  For a long time, the fastest algorithm for finding the shortest path
on a triangulated 2-manifold was the 1996 Chen and Han algorithm, which runs in $O(n^2)$ time for
a surface of $n$ vertices. Here is an example from an implemention of mine with students
of this algorithm,
showing the shortest paths from one point to all the vertices of a convex polyhedron:



This and other algorithms are described in
Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Section 24.2.
There was effort over many years toward improving the time complexity in the special case of surfaces of convex polyhedra,
which was finally cracked by
Schreiber and Sharir in their remarkable paper,

Schreiber, Yevgeny, and Micha Sharir. "An optimal-time algorithm for shortest paths on a convex polytope in three dimensions." Discrete Comput. Geom.,  Springer, 39 (2008), 500-579; Twentieth Anniversary Volume, 2009. 1-80.
  (Here is the earlier conference version.) 

They improved the speed to $O(n \log n)$;
the shortest paths are represented implicitly to avoid the $n^2$ complexity of explicit listing.
This time complexity has only been achieved to-date for subclasses of nonconvex surfaces.
