Duo maintains a contacts list. It doesn't seem too big of a leap to assume Messages queries Duo to see if both parties have the app installed. Or, as others have suggested, it may take them to an app installation page on either the Play Store or App Store.