On Debian and derivatives, the package you’re looking for is gcc-arm-none-eabi:

apt install gcc-arm-none-eabi

To find this out yourself in future, install apt-file, update your indexes and use it to search for commands:

apt install apt-file
apt-file update
apt-file search bin/arm-none-eabi-gcc

I found the solution based on the discussion available at https://unix.stackexchange.com/questions/377345/installing-arm-none-eabi-gcc and the documentation available on https://mynewt.apache.org/latest/get_started/native_install/cross_tools.html#installing-the-arm-cross-toolchain.

The name and structure of the software changed over time. The arm-none-eabi-gcc is gcc-arm-none-eabi now, and so on.

$ sudo apt-get remove binutils-arm-none-eabi gcc-arm-none-eabi
$ sudo add-apt-repository ppa:team-gcc-arm-embedded/ppa
$ sudo apt-get update 
$ sudo apt-get upgrade
$ sudo apt-get install gcc-arm-none-eabi
$ sudo apt-get install gdb-arm-none-eabi 

And finally, to verify the downloads, you can run the following commands:

arm-none-eabi-gcc --version
arm-none-eabi-g++ --version
arm-none-eabi-size --version 

Worked for me on Ubuntu 16.04:

sudo apt install gdb-arm-none-eabi