On my Debian unstable machine, I followed the official Ubuntu instructions and only changed the following step:
echo "deb [arch=amd64] https://brave-browser-apt-release.s3.brave.com/ $UBUNTU_CODENAME main" | sudo tee /etc/apt/sources.list.d/brave-browser-release-${UBUNTU_CODENAME}.list
to this:
echo "deb [arch=amd64] https://brave-browser-apt-release.s3.brave.com/ bionic main" | sudo tee /etc/apt/sources.list.d/brave-browser-release-bionic.list
Then I also added the following in /etc/sysctl.d/00-local-userns.conf:
kernel.unprivileged_userns_clone = 1