There are a few things you can do to improve on other answers. Since iOS 9, a link can be opened in a UIWebView or in a SFSafariViewController. You might want to handle them differently.
The SFSafariViewController shares cookies across apps, and with the built in Safari. So in your app you can make a request through a SFSafariViewController that will set a cookie that says "my app was installed". For instance you open your website asking your server to set such cookie. Then anytime you get a request from a SFSafariViewController you can check for that cookie and redirect to MYAPP:// if you find it, or to the app store if you don't. No need to open a webpage and do a javascript redirection, you can do a 301 from your server. Apps like Messages or Safari share those cookies.
The UIWebView is very tricky since it is totally sandboxed and shared no cookies with anything else. So you'll have to fallback to what has been described in other answers:
window.onload = function() {
  var iframe = document.createElement("iframe");
  var uri = 'MYAPP://';
  var interval = setInterval(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);
  iframe.onload = function() {
      clearInterval(interval);
      iframe.parentNode.removeChild(iframe);
      window.location.href = uri;
  };
  iframe.src = uri;
  iframe.setAttribute("style", "display:none;");
  document.body.appendChild(iframe);  
};
I've found it annoying that this will prompt the user if they want to leave the current app (to go to your app) even when your app is not installed. (empirically that seems only true from a UIWebView, if you do that from the normal Safari for instance that wont happen) but that's all we got!
You can differentiate the UIWebView from the SFSafariViewController from your server since they have different user agent header: the SFSafariViewController contains Safari while the UIWebView doesn't. For instance:
Mozilla/5.0 (iPhone; CPU iPhone OS 10_3 like Mac OS X) AppleWebKit/603.1.30 (KHTML, like Gecko) Mobile/14E269
-> UIWebView
Mozilla/5.0 (iPhone; CPU iPhone OS 10_3 like Mac OS X) AppleWebKit/603.1.30 (KHTML, like Gecko) Version/10.0 Mobile/14E269 Safari/602.1
-> SFSafariViewController
Other considerations:
- in the first approach, you might want to handle uninstalls: if the user uninstalls your app, you still have a cookie that says that the app is there but it's not, so you might end up with the "Can not open URL"message. I've handled it by removing the cookie after a few tries that didn't end up opening the app (which I know because at every app open I'm resetting this failed tries cookie)
- In the second case, it's unclear if you're better off using a setIntervalorsetTimeout. The issue with the timeout is that if it triggers while a prompt is on, it will be ignored. For instance if you open the link from Messenger, the os will ask you "Leave Messenger? You're about to open another app" when the iframe tries to load your app. If you don't respond either way within the 500ms of the timeout, the redirection in the timeout will be ignored.
- Finally even though the UIWebViewis sandboxed, you can give it a cookie to identify it, pass it in your deeplink, and save this id as corresponding to device with your app in your server when your app opens. Next time, if you see such a cookie in the request coming from theUIWebView, you can check if it matches a known device with the app and redirect directly with a 301 as before.