Você pode usar aplicativos gráficos como GParted no Ubuntu. Instale-os dos repositórios usando:
sudo apt-get install gparted
Uma vez instalado, selecione o dispositivo / partição de bloco correto e formate-o usando um sistema de arquivos como ext2 / 3/4, JFS, XFS, ResiserFS, etc., dependendo de suas necessidades.
No entanto, os sistemas de arquivos mencionados acima são apenas para referência. Nem todos eles correm em todas as distribuições perfeitamente.
Por exemplo, como apontou @Nils:
RiserFS is not suppported any more on some major distributions.
JFS and XFS can be too new for some distributions. Ext2 is too old.
Ext2 é quase um sistema de arquivos herdado e não é uma boa escolha.
Isso deixa apenas Ext3 e Ext4.
Novamente, como o ext4 ainda é novo e está em desenvolvimento, ele pode ter problemas com algumas distribuições. Por exemplo, no RH5 não há ext4, no SLES10 é um pouco arriscado. No entanto, devo salientar aqui que o kernel Linux vanilla suporta completamente o ext4 desde a versão 2.6.28. No Arch e no Gentoo ext4 não apresenta problemas.
Mas o ext3 funcionará em qualquer distribuição atual - não apenas nos mais novos.