結論

iOS15でPHPickerのNavigationBarの色を変更するのはおすすめしない。

Apple Developer Forumsに「どう変更するのか」と質問すると、AppleのFrameworks　Engineerの方から以下の回答が返ってきた。

PHPicker is out of process and currently doesn't support any UI customization, other than inheriting your application's tint color.
We recommend just using the default system picker UI. Most users already used PHPicker in other apps, and familiarity could help them trusting your app.
However, please submit an enhancement request via the Feedback app, if you think your app needs specific customization options.
https://developer.apple.com/forums/thread/701712

要約すると「PHPickerではUIのカスタマイズをサポートしてない。デフォルトのUIを使用することを勧める。」とのこと。
というわけで、iOS15ではNavigationBarの色を変えずにデフォルトのUIのままにした方がよさそう。

iOS15でNavigationBarの色を変更しようとするとどうなるか？

まず、iOS15からNavigationBarの色をカスタマイズするには、以下のようにAppearanceで設定する必要がある。

    if #available(iOS 15, *) {
        let navigationBarAppearance = UINavigationBarAppearance()
        // NavigationBarを不透明な状態にする
        navigationBarAppearance.configureWithOpaqueBackground()
        // アプリ内全てのNavigationBarの背景色を赤に設定
        navigationBarAppearance.backgroundColor = .red
        UINavigationBar.appearance().standardAppearance = navigationBarAppearance
        UINavigationBar.appearance().scrollEdgeAppearance = navigationBarAppearance
        UINavigationBar.appearance().compactAppearance = navigationBarAppearance
    } else {
        // iOS14以下の場合はbarTIntColorで背景色を設定する
        UINavigationBar.appearance().barTintColor = .red
    }

上記コードをAppDelegate.swiftなどで適用すると、以下のようにアプリ全体でNavigationBarが赤くなる

iOS15	iOS14

（若干iOS14の方が色が薄いのも気になる）
この状態でPHPickerを開くと、期待値としてはPHPickerのNavigationBarにも赤色が付与されることであるが...

iOS15	iOS14

iOS15ではデフォルトの色のまま表示されてしまう。
iOS14では問題なく赤色が適用されている。

どうやらiOS15からは今まで通りのような方法では変更できなさそう。

それでも色を変更したい...！

どうしてもPHPickerの色を変更したい場合、以下の方法がある
変更したい色を画像として出力し、NavigationBarに貼り付ける方法である。

    let navigationBarHeight = UINavigationController().navigationBar.frame.height
    let size = CGSize(width: UIScreen.main.bounds.width, height: navigationBarHeight)
    let renderer = UIGraphicsImageRenderer(size: size)
    let image = renderer.image { context in
        // 画像を赤で塗る
        UIColor.red.setFill()
        context.fill(context.format.bounds)
    }
    UINavigationBar.appearance().setBackgroundImage(image, for: .default)

上記コードを適用すると

シミュレータ	実機

ん？シミュレータではいい感じに適用されていて問題なさそうだが、実機ではSearchBarが表示されているぞ...？　しかも色が適用されてない。
そう。不具合なのか不明だが、シミュレータでPHPickerを開いた時にはなぜかSearchBarが表示されないようだ。

一応この状態でも、SearchBarをタップすることでSearchBarにも色が適用されるようになっている。

SearchBarをタップしなくてもPHPickerを開いた時に既に色が適用されているように変更してみる
アプリ全体のSearchBarの背景色を変えることで実現できる

    UISearchBar.appearance().backgroundColor = .red

ぱっと見は問題なさそうだが、色を画像として貼り付けてた影響により、NavigationBarが半透明な状態になってしまっている。
SearchBarは不透明なため、よくみると違和感がある。

これを回避するために、UINavigationBar.appearance()自体に.backgroundColorを設定することで不透明にできる。（なぜこうなるのかは不明）

    UINavigationBar.appearance().backgroundColor = .red

以上でPHPickerの背景色を変更することはできる。

NavigationBarItemの色の変更

iOS15のPHPickerでも「キャンセル」「追加」などのNavigationBarItemの色自体は従来の方法で変更できる。

    UIBarButtonItem.appearance().tintColor = .green

まとめ

冒頭の結論の通り、iOS15ではPHPickerのNavigationBarの色を変更するのはお勧めしない。
紹介した通りのトリッキーな方法でなんとか色をつけることもできるが、Apple的にはデフォルトのUIのままPHPickerを使用してほしいからである。
iOS15でUIのカスタマイズをサポートしてないのであれば、今後登場するであろうiOS16以降でも同様にサポートしない気がする
これは憶測になるが、iOS15からAppleはかなりプライバシー周りのことを強化しているイメージがあり、PHPickerも写真という個人情報満載の画面を提供するViewControllerなため、Apple的には開発者側があまりPHPickerに介入できないようにしているんじゃないかと思う