Bem, existem duas rotas que você pode seguir com isso: Ou você pega a porta de código aberto do Minecraft, chamada Minetest-c55. Eu deveria avisá-lo, porém, não é tão completo em termos de novos recursos adicionados ao Minecraft ultimamente.
Ou, você encontra um repositório não oficial para o sun-java, que é o que Notch recomenda para executar o verdadeiro minecraft.
No entanto, você não deve - a julgar por este artigo - ter um problema com isso em uma instalação padrão do Ubuntu