Great question. Rather than sharing a deep link that leads directly to your app, you should host a page on your website with fallback code in Javascript. That page can either open the app directly or fall back to the App Store (rather than your website).
Here is a concrete example of the page you would need to host on your server and link to on Facebook. It also works for emails, social media, etc. Simply substitute in your app's URI and your app's App Store link. Note that the iframe works on a greater number of browsers.
<!DOCTYPE html>
<html>
<body>
<script type="text/javascript">
window.onload = function() {
// Deep link to your app goes here
document.getElementById("l").src = "my_app://";
setTimeout(function() {
// Link to the App Store should go here -- only fires if deep link fails
window.location = "https://itunes.apple.com/us/app/my.app/id123456789?ls=1&mt=8";
}, 500);
};
</script>
<iframe id="l" width="1" height="1" style="visibility:hidden"></iframe>
</body>
</html>
So, if the user has your app installed, the link with the URI will succeed and the user will leave the browser before the script for redirecting to the App Store can be triggered. If the user does not have your app, the redirect succeeds (after a brief error message).
Disclosure: I'm a developer at the Branch Metrics and the above code is part of our solution to this issue.