A teoria
A definição mais aceita é que a linguagem precisa ser Turing-Complete, ou que pode simular a Universal Turing Machine para ser considerada de programação. Isso significa que qualquer função que pode ser matematicamente calculada de alguma forma, deve ser possível ser expressada, e consequentemente executada em sua plenitude, gerando resultados corretos e esperados através dessas linguagens.
A teoria não fala da forma como isso pode ser obtido, mas obviamente é preciso conseguir o objetivo por meios próprios, ela não pode depender de formas externas ao que foi definida nela para alcançar o resultado.
A teoria não fala qual é o meio concreto de execução. Não importa que isso seja convertido para outra linguagem ou código que realmente permita executar o cálculo, é normal que isso aconteça.
A teoria também não fala sobre a arquitetura da máquina que vai executar, não precisa ser elétrica, não precisa ter um processador.
Ela deixa em aberto que a linguagem possa expressar o problema da forma mais simples ou mais complexa, facilitando ou dificultando para humanos ou máquinas entenderem o que é aquilo (obviamente estas duas características são antagônicas, o que é fácil para o primeiro, é difícil para o segundo e vice-versa). Não importa se ela é representada por bits ou algo mais esotérico que isto (sim é possível algo maluco, inventado) ou um texto poético usando versos pinçados dos grandes autores lusófonos no melhor e mais rebuscado português (se é que isto é possível existir).
Hardware
O ábaco era um dispositivo de computação (uma pena não ser mais usado nas escolas, deve ser por isso que as pessoas não conseguem mais fazer uma simples conta de porcentagem), mas ele não possui uma linguagem de programação, não há como expressar funções matemáticas nele. O mesmo vale para todas as máquinas mecânicas e até algumas eletromecânicas até a década de 40 (do século 20, vai que isto sobreviva umas 3 ou 4 décadas e as pessoas do futuro se confundam :) ).
O computador moderno surgiu durante uma rápida evolução durante a segunda guerra mundial (sempre o uso militar sendo a força por todo empurrão na tecnologia). Ali surgiu o computador que conseguia fazer todo tipo de cálculo de forma abstrata, automática e principalmente programável, ainda que de uma forma rudimentar.
É possível que outras máquinas possam ter tido a capacidade de programação, mas por não ter outras características ficaram menos famosas, acabaram sendo relegadas a um galho da evolução que não foram pra frente.
A representação do programa era manual e não tenho referências de como faziam. Sei que era inserido por chaves através de codificação binária, mas provavelmente havia algo em um nível mais alto sendo realizado no papel antes de chegar nisso.
Já havia uma linguagem de programação de baixo nível nesse dispositivo. E provavelmente já usavam outra linguagem antes.
Primeiras linguagens
Ficou claro na época que linguagens de maior nível eram necessárias. O Assembly logo foi inventado e depois montadores para converter este código em algo mais baixo nível. Principalmente depois que a entrada de dados pôde ser feita de forma mais conveniente do que chaves binárias, como a leitura de cartão perfurado através de uma máquina de escrever adaptada.
Depois surgiram linguagens que começaram se aproximar da notação usada na matemática e o uso do inglês. Fortran foi a primeira que tinha boa organização e fez sucesso por ser um claro passo à frente.
Veja o timeline da criação das linguagens de programação (melhor esforço possível).
Componentes necessários
Vou correr o risco de errar aqui, estou falando algo que eu vejo acontecer e não estou seguindo uma definição formal. Então para resolver qualquer problema computacional é preciso ser capaz de:
- armazenar - e ler obviamente - dados em um lugar qualquer pelo menos de forma transitória - manter estado (não é I/O);
- transformar dados de forma a expressar as operações matemáticas mais simples (eu diria que a adição e multiplicação na sua forma mais básica são necessárias);
- manter um sequência de "execução" - organizar logicamente os armazenamentos e transformações;
- desviar a sequência;
- tomar uma decisão entre pelo menos 2 "caminhos".
Posso ter esquecido de alguma coisa ou posso ter colocado algo que já é uma abstração de outra citada.
Algumas pessoas podem dizer que as três últimas podem ser definidas como ter a capacidade de recursão. É uma forma de dizer, mas não sei se todo mundo entenderá isto. E não sei se isso já não é abstrair um pouco o conceito.
Não é à toa que as linguagens que fazem sucesso são as imperativas, mesmo que elas carreguem algum outro paradigma para auxiliar.
Mais informações em:
Coloquei no GitHub para referência futura.