Experimente este tutorial: (baseado no download da versão Java, em vez de .sh)
---- ---- UPDATE ---- ----
O arquivo .sh , uma vez baixado, é executado corretamente no Ubuntu 12.04 (64 bits).
Após a instalação, basta executar isso na linha de comando:
~/yEd/yEd &
Com um pouco mais de esforço, provavelmente posso obter um ícone do Unity (e colocá-lo no dock).