O console de saída não é o que você está pensando:
Quando o programa Java é executado, o ambiente que o executa passa quais serão as formas de entrada e saída de dados associadas aos objetos System.in, System.err e System.out.
System.out é um objeto do tipo PrintStream, ou seja, onde Stream significa uma correnteza de dados em uma mão só, ou você somente manda dados ou somente os recebe. No momento que algo imprimido no System.out, a stream vai somente para a frente. Por isso que não é possível voltar e imprimir algo no mesmo lugar, esta função pertence à ao sistema de janelas usado recebe o resultado do System.out.
Quando o programa é executado pelo Eclipse, Netbeans, qqr IDE, este System.out é associado à janela de console de saída da IDE.
Quando o programa é executado por um Prompt de Comandos, seja o cmd.exe do Windows, ou um Terminal em sistemas Unix-like, o System.out também é associado às suas janelas.
No caso, CLS é um comando DOS que limpa a tela e esse comando existe somente no cmd.exe. Este comando não manipula o System.out, ele somente manipula a janela associada a ele (normalmente ele somente pula 20-25 linhas, o tamanho da tela).
Caso queria imprimir algo sempre no mesmo local da janela(num Prompt/Terminal e não os consoles das IDEs), ou seja, manipular o cursor da janela, você precisa de uma biblioteca de interface de usuário baseada em texto. Em Linux a mais famosa é o NCurses, só que ela é nativa ao sistema. Se quiser algo parecido em Java, existe o Java Curses, e outro que faz tempo que não é atualizado chamado CHARVA.
Edit: Desde o Java 6 também existe uma classe Console, que acessa o console associado a VM.