Same as any other messenger app, by grabbing your contact list. When you open Duo it will show you a list of your contacts that are duo-able.
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.
I don’t know that they necessarily do based on the article? Link might lead to a setup page.