Linguagem de programação
Cada uma tem que definir o que ela quer dizer com isso. Mas no geral eu diria que é criar uma nova sintaxe, normalmente através de metaprogramação.
Os mecanismos podem ser mais simples, desde o pré-processador do C, até macros bem sofisticadas que podem até envolver o compilador.
É muito comum que estas linguagens sejam apropriadas para DSLs. Um exemplo.
Em geral isso é bem problemático e costuma fazer xixi na mão de quem não é muito bom em lidar com toda complexidade. Linguagem de programação explode em possibilidades de combinações. Desde "pequeno" eu queria fazer uma linguagem assim, hoje sei como isto é quase inviável para um produto que vá além de um nicho muito específico ou pesquisa acadêmica.
Algumas linguagens forçam a barra dizendo que são extensíveis porque dá para estender alguma coisa, mas pouco.
Wikipedia.
Linguagem declarativa
Existem linguagens declarativas que já são DSLs que permitem a criação de novas declarações de forma simples. Apesar de algumas delas serem extensíveis por definição, não vi nada oficial indicando que elas sejam consideradas "linguagens extensíveis", então apesar do termo caber, ele é usado em um contexto diferente.
Veja.
Coloquei no GitHub para referência futura.