Em todas as versões atualmente suportadas do Ubuntu, abra o terminal e execute:
sudo apt-get install python-bs4
O Beautiful Soup (python-bs4) é um analisador de HTML tolerante a erros para o Python 2.x. 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 Python: IDLE e IDLE 3 para executá-los.