Primeiro entenda que a avaliação sempre será subjetiva, ainda que possa haver critérios objetivos.
A definição do dicionário é boa. Claro que não ajuda entender os pontos a considerar, mas também acredito que nem em um livro dá para definir de forma concreta. E existem vários que tentam fazer isso.
Obviamente que todo código elegante é correto, isso eu coloco como hors concours. Não basta "funcionar", tem que ser correto. Ele faz o que deveria fazer em qualquer situação planejada e lida bem com as situações não planejadas.
Acho que a principal característica é o código ser legível por profissionais qualificados. Note a diferenciação. Ser legível para leigos, estudantes, amadores os pseudo-profissionais não é um requisito para ser elegante. O código deve ser facilmente percebido, ainda que eventualmente precise de comentário que façam sentido.
Outra característica muito forte é que ele deve ser simples, estúpido. O problema pode ser complexo, a solução deve ser simples, que é o oposto de complicado.
Ser um código limpo é outra característica. Não deve ter nada que não precise. Não deve ter mais de uma responsabilidade. Mas também não deve encurtar ao ponto de não ser fácil entender o que está ocorrendo ali. De nada adianta criar um monte de camadas para atingir este objetivo e piorar outro.
O código deve ser claro e expressar bem o que deseja. Deve ser uma solução óbvia. Deve ser tão conciso quanto possível sem comprometer a legibilidade. Para isso deve ter as abstrações certas, e o nível abstrativo adequado.
Geralmente ele deve fazer da forma como já é conhecida por todos e não tentar inventar uma forma esquisita sem necessidade. Deve escolher os algoritmos adequados. Não reinventar a roda, no bom sentido.
Deve seguir convenções de codificação estabelecidas em termos gerais, pela linguagem e pela equipe. Assim fica mais fácil acompanhar o que está escrito. Código elegante está bem formatado, não tem brancos demais e nem de menos (vertical ou horizontal). Não tem abreviaturas desnecessárias, usa nomes significativos.
Deve ter uma forma que facilite a manutenção e evite bugs. Você pode confiar no código. Pode mudar sem susto?
Provavelmente ele não deve fazer otimização prematura. Mas ele deve ser tão rápido quanto possível sem comprometer outras características. E é claro que deve ter a performance desejada, se possível. Mas mais que ser rápido, ele precisa ser eficiente.
Não deve ser clever. Essa é uma palavra geralmente usada para indicar que o programador tentou fazer um código muito inteligente, performático, curto, que parece fazer algo curioso, que se aproveita de alguma característica da linguagem ou da matemática para obter o resultado, mas que não é facilmente compreensível. Clever code pode parecer elegante, mas é o oposto.
Você só obtém isso se domina a computação (no sentido matemático e técnico), sabe como o computador, a linguagem e outros recursos funcionam.
Só pode fazer código elegante se entende o problema que está resolvendo e fez um planejamento prévio do que precisa, do que pode dar errado, de todas necessidades.
Então dá para dizer que só escreve código elegante sempre, quem tem experiência, e não é teimoso :) Claro que copiar código elegante de outros faz aquele trecho elegante, mas pra produzir código inovador elegante precisa "chão".
Elegância é fazer o que é mais adequado para aquele caso. E seguir regras prontas cegamente não ajuda muito. Por isso boas práticas não ajudam diretamente a fazer código elegante. São coisas distintas.
O código elegante é, possivelmente, aquele que alguém te mostra como você poderia ter feito e você fala "por que eu não pensei nisso antes?" :).
Um código WTF não é elegante.
Tem linguagens que incentivam código elegante, outras nem tanto.
Ficou mais claro? Talvez não, mas é o tipo de coisa que não se mostra no papel. Como o nome indica, envolve (bom) gosto.
Coloquei no GitHub para referência futura.