Você precisa de um tempo de execução Java para executar o jogo.
Para instalá-lo, execute sudo apt-get install openjdk-7-jre
em um terminal. Você pode então rodar o jogo clicando duas vezes no arquivo .jar (se ele abrir no Archive Manager, clique com o botão direito do mouse e selecione Open With > OpenJDK) ou em um terminal executando java -jar ./StarMade-Starter.jar
da pasta onde o arquivo é armazenado.