Basicamente é a programação que estrutura a execução através de rotinas estanques que são chamadas conforme a necessidade. Normalmente as chamamos de funções, mas não precisa ser exatamente essa forma.
Normalmente essas rotinas possuem parâmetros para se comunicar com as outras partes do código e pode retornar algum valor, mas não é obrigatório, apesar de ficar confuso misturar tudo ou pouco poderoso não permitir nenhuma comunicação.
Certamente a definição disso não é "uma programação baseada em procedures (procedimentos)". Bom, até é, mas tem que tomar cuidado porque o procedimento é um mecanismo de rotina estanque. Um que é pouco usado na maioria das linguagens modernas de forma explícita. Claro que uma função que retorna nada (em geral void
) não deixa de ser um procedimento. O termo procedural é usado como forma genérica.
Assim como programação funcional não é "aquela que tem funções", até porque se fosse o caso quase toda linguagem seria funcional.
O paradigma procedural é secundário e se refere mais à organização do código como um todo, assim como também é a orientação a objeto.
O principal que difere o procedural do orientado a objeto é que o primeiro glorifica os procedimentos, o comportamento, e o segundo glorifica o objeto, o estado (curiosamente os escondendo).
[...] a programação procedural é uma evolução da programação estruturada [...]
A programação estruturada se preocupa só com o fluxo do código e não a sua compartimentação.
[...] programação procedural é algo que, até certo ponto, inevitável [...]
Não concordo que seja inevitável o uso do procedural. O imperativo é quase inevitável. Falo isso em O que é paradigma?.
[...] às vezes utilizado como sinônimo de programação imperativa [...]
É usado erroneamente como sinônimo de imperativo.
Coloquei no GitHub para referência futura.