Em todas as versões atualmente suportadas do Ubuntu, abra o terminal e execute:
sudo apt-get install python3-bs4
python3-bs4 é um analisador HTML tolerante a erros para Python 3. Você pode ver a partir disso que existem dois pacotes diferentes: python-bs4 (para Python 2.x) e python3-bs4 (para Python 3.x) e, para evitar que você fique confuso, há também dois Ambientes de Desenvolvimento Integrados diferentes para o Python: IDLE e IDLE 3 para executá-los.