Where are Email Messages Stored?
The Mail.app stores all Messages in your User Directory:
~/Library/Mail/
Depending on your OS Version there is a Subfolder, f.e. "V3" for 10.11 and "V2" for 10.10., containing Subfolders for each Mailbox.
The Library Folder is usually hidden, but you can access it in the Finder from the Menu "Go to" > "Go to Folder" (or CMD+SHIFT+G) and typing in the Path listed above.
You can actually restore mail messages directly inside Mail. Make the Mail application active, then enter Time Machine via the menulet. Works similar to file recovery in Finder.