Is this graph showing the average temperature on Earth going back millions of years accurate?
In a word, no.

The graph is based on work by Chris Scotese. The climate science site RealClimate.org has this to say about it:


  Scotese is an expert in reconstructions of continental positions through time and in creating his ‘temperature reconstruction’ he is basically following an old-fashioned idea (best exemplified by Frakes et al’s 1992 textbook) that the planet has two long-term stable equilibria (‘warm’ or ‘cool’) which it has oscillated between over geologic history. This kind of heuristic reconstruction comes from the qualitative geological record which gives indications of glaciations and hothouses, but is not really adequate for quantitative reconstructions of global mean temperatures. Over the last few decades, much better geochemical proxy compilations with better dating have appeared (for instance, Royer et al (2004)) and the idea that there are only two long-term climate states has long fallen by the wayside.


and


  Some better examples of long term climate change graphics do exist. This one from Veizer et al (2000) for instance (as rendered by Robert Rohde):




For a more detailed discussion of graphical reconstructions, see this RealClimate entry