結論

shellをRosettaで起動してnodebrew installを実行

手順

Finderアプリでアプリケーションフォルダを開く
shellアプリを右クリック
「情報を見る」をクリック
「Rosettaを使用して開く」にチェックを入れる
Shellを起動
nodebrew installを実行

何故インストールがうまくいかないのか

これはAppleシリコンのCPUを搭載したMac古いNodeをインストールしようとした時に発生します。
nodebrewでインストールできるM1チップに対応しているnodeバージョンに古いNodeバージョンがないためNotFoundとなりインストールがはじまらないのが原因となる。
ちなみにnodebrew ls-remoteでは普通に表示されるので勘違いしやすい。

一応バイナリのものをコンパイルすることができるらしいが、これもうまくいかないことが多いので、Rosettaを使うのが一番簡単で安全と言える。