I deleted a contact in Marketo, but it exists in Salesforce. Will that record be synced back to marketo? If yes, when and how?

It will sync back to Marketo as soon as it's modified in SFDC

If you want to prevent some SFDC leads from syncing to Marketo,

1. create a custom field called "Sync to Marketo"
2. submit a support case to Marketo, and ask them to set up the integration on the backend to only sync leads where that field is checked

You can then either manually uncheck the box for leads you don't want to sync to Marketo, or create a formula field or workflow  in SFDC, or a campaign in Marketo, to manage whether the box is checked or unchecked.

Amanda, do you know if Marketo would set up the integration if I'd rather have a checkbox for "Do Not Sync To Marketo?" So the box being checked would prevent syncing to Marketo. Thanks!