In a few newbie words - AppLink is a webpage full of meta headers. These meta headers redirect the client to appropriate application or store on their device.
E.g. if you create an AppLink page for MyXYZapp, which is an app for both iOS and Android, than probably you'll have a pseudo code in your AppLink page header like this:
//client is visiting the applink:
if the client is on Android:
 try:
  open app with bundle id `com.AndroidCompany.MyXYZapp` 
 else if MyXYZapp is not present on the device:
  redirect client to Play Store page of MyXYZapp
else if the client is iOS:
 try:
  open `com.iOSCompany.MyXYZapp`
 else:
  redirect to AppStore page of MyXYZapp
else if client is visiting from any other OS:
 redirect to AppStore / PlayStore via browser (or create your own behaviour)
EDIT:
Facebook itself now provides applinks, as described here:
https://developers.facebook.com/docs/applinks/index-api/
EDIT, THIS NO LONGER WORKS:
Now most people do not own servers to host these kinds of pages so facebook offers free hosting and very easy tool to generate AppLinks for your apps:
https://developers.facebook.com/quickstarts/?platform=app-links-host
read more here:
https://developers.facebook.com/docs/applinks/hosting-api
p.s. hope the URLs don't decay and dissolve through the coming centuries
p.p.s the URLs have decayed under 2 years. Crazy