Blah, this must be the fourth time I've forgotten the proof, so this is a service to my future self:

First note that it suffices to find one internal diagonal in a simple polygon, since that will cut it into two simple polygons and induction completes the triangulation. Pick a vertex at which the angle is less than . Let be the adjacent vertices. Either is the internal diagonal we want, or it intersects the boundary, in which case, let be the vertex of the polygon in triangle that is furthest from . It exists and is an internal diagonal.

(It's the proof cited in Proofs from the Book and also appears in an unnamed PDF hosted on princeton.edu you can find by searching.)

Also, an unsolved-by-me question: if is a vertex of a simple polygon at which the angle is greater than , does there necessarily exist another vertex such that is an internal diagonal (i.e. lies strictly inside the polygon, except, of course, for its endpoints)?

edit: I see now. The answer is yes; all you have to do is rotate a ray starting at around it and see the first time that the first edge of the polygon the ray hits changes. At that instant, the ray must be passing through a vertex, and connecting that vertex to does the trick. (If 's angle is less than then it's possible the ray only hits one edge throughout the entire rotation, so this fails.)