ちょっと仕組みがわからなくてもやもやしていたので、調べました。
間違っていたら教えて下さい

deep link

以下のドキュメントにDeepLinkの説明があるのですが、Navigationの特定のFragmentなどに遷移できるという説明がありますが、起動方法は書いてあってもIntentなどで起動した後のハンドリング方法は書いていません。ハンドリングせずにどのように遷移するのか謎でした

Create a deep link for a destination
https://developer.android.com/guide/navigation/navigation-deep-link

explicit deep linkの場合
通知などから起動したい場合に明示的にdistinationを指定して起動できます。

val pendingIntent = NavDeepLinkBuilder(context)
    .setGraph(R.navigation.nav_graph)
    .setDestination(R.id.android)
    .setArguments(args)
    .createPendingIntent()

implicit deep linkの場合(urlによる遷移)

またはnavigationのxml内で以下のように宣言して、AndroidManifest.xmlでnav-graphを指定します。

navigation/navigation.xml

<deepLink app:uri="https://www.google.com" />

AndroidManfiest.xml

        <activity name=".MainActivity" ...>
            ...

            <nav-graph android:value="@navigation/nav_graph" />

どのようにハンドリングを開始するか？

どうやらNavHostFragmentが作られたときにhandleDeepLink()が呼ばれて、遷移するようです。

    private void onGraphCreated(@Nullable Bundle startDestinationArgs) {
...
        if (mGraph != null && mBackStack.isEmpty()) {
            boolean deepLinked = !mDeepLinkHandled && mActivity != null
                    && handleDeepLink(mActivity.getIntent());

普通にドキュメントもあるので、自分で明示的に使うこともできるようです。
https://developer.android.com/reference/androidx/navigation/NavController.html#handleDeepLink(android.content.Intent)

ドキュメントには以下のようにあります。

Checks the given Intent for a Navigation deep link and navigates to the deep link if present. This is called automatically for you the first time you set the graph if you've passed in an Activity as the context when constructing this NavController, but should be manually called if your Activity receives new Intents in Activity.onNewIntent(Intent).

基本的には自動的に呼ばれるけれども、アプリ内で発行したい場合はActivity.onNewIntentでNavController#handleDeepLink呼び出してあげる必要がありそうです

どのように遷移するか？

ではhandleDeepLink()ではどのように遷移するのでしょうか？

explicit deep linkの場合

PendingIntentの中のExtraにdestinationのリストが渡されるので、それで遷移しています。
ちなみにどのようにスタックを積むかというとnav graphをネストして、startDestinationを指定していくことでできるのですが、ここでは省略します。

implicit deep linkの場合(urlによる遷移)

AndroidManfiest.xmlにてnav-graphを指定することで、intent-filterが定義されて、ActivityがURL反応するようになりますが、それだけでは指定のFragmentに遷移することはできません。ここでも同様にhandleDeepLink()が呼び出されるようで、

こちらはintentのgetData()からURLを取得して、そこから探してくるみたいです。

handleDeepLink()内

        if ((deepLink == null || deepLink.length == 0) && intent.getData() != null) {
            NavDestination.DeepLinkMatch matchingDeepLink = mGraph.matchDeepLink(intent.getData());
            if (matchingDeepLink != null) {
                deepLink = matchingDeepLink.getDestination().buildDeepLinkIds();
                bundle.putAll(matchingDeepLink.getMatchingArgs());
            }
        }