How to recover an accidentally deleted new pages document
For anyone else that might have done this, here is my solution:

I created another new document with a unique string and searched spotlight to find the directory where autosaved Pages files live. With that directory open in Finder, I could use Time Machine to find the old autosaved file ("Unsaved Pages Document.pages") from an hour ago.

For me the directory was: 


  ~/Library/Containers/com.apple.iWork.Pages/Data/Library/Autosave
  Information