The distro is actually Pop_OS, but I seem to remember having to do this in Debian as well.
The GitHub Powerline page says that you can just install the fonts-powerline package through apt and angels will sing. I did not have any such luck. The way I finally got it to work was to actually clone Powerline from GitHub and use the included installer. This, of course, was after several evenings of trying to track down various settings and endless restarts. Just skip to the end and install them from GitHub. Then you’ll have the ‘…for Powerline’ fonts available to you and tmux and vim powerlines will look right in urxvt.
If you’re just using gnome-terminal, the aforementioned fonts-powerline package is all you need.