The answer is that it depends on who your ISP is, and what type of email account you have. If you are using an IMAP account, then all the emails are stored on the server, with your mac syncing to that server.
When you delete emails from one mac, they are deleted on the server, and your other mac will then sync and delete them as well.
Whether you can retrieve them will depend upon where they got deleted to, and what happened to them there. Try looking in the Trash to see if the emails were deleted just to there, or whether the Trash was subsequently emptied.
What email accounts are you using?
Cheers,
Joel