É algo abstrato. É algum "documento" que estabelece regras a serem seguidas, o que se espera das possíveis implementações. Essas regras podem exigir algumas coisas e proibir outras. É uma formalização de como algo deve proceder. É a lei. Grosso modo, é a receita.
É algo concreto. É como é feito de verdade. É o que existe para ser usado. É a aplicação da lei. É o bolo feito por alguém atendendo o que diz a receita.
É possível variar a receita, mas se modificar pontos fundamentais dela, estará ferindo o prato e ele não pode mais receber aquele nome. Obviamente que na culinária causa menos problema que na computação :P.
Relação entre elas
É óbvio que se a implementação não faz algo que a especificação obriga ter, quem for usar aquilo, que deve ser um padrão, terá problemas. Se a implementação faz algo extra que a especificação não proíbe não haverá problemas. Mas se for usar o que foi criado em cima desta implementação aproveitando os extras, obviamente não poderá portar para uma implementação diferente que se atenha mais restritamente à especificação.
No contexto descrito a implementação está sendo feita em cima da especificação, atendendo todas as regras estabelecidas por ela. A implementação pode, em tese, fazer qualquer coisa que não esteja proibida pela especificação, mas isso pode trazer dificuldades, até futuras em uma revisão da especificação.
Dentro das regras a implementação pode e deve fazer o melhor possível para atender as necessidades dos seus usuários.
Se a implementação ferir uma regra da especificação ela não poderá ser considerada como aderente àquele padrão.
A especificação pode ser mais detalhada ou mais superficial, dando mais rigidez ou flexibilidade ao que a implementação pode fazer. Também pode dar mais ambiguidade e trazer problemas. Especificação pode ter bug :).
Costuma ser mais difícil fazer uma boa especificação do que uma boa implementação, ainda que a quantidade de trabalho possa ser o inverso.
Uma especificação ruim pode dificultar ou até inviabilizar uma boa implementação existir.
Normalmente a especificação deve ser simples de entender. A implementação deve ser boa de usar.
Alguns domínios funcionam melhor com uma especificação clara e formal existente. Outros podem ser só um complicador desnecessário e indesejável.
Planejar como vai implementar não é especificação, pelo menos não no sentido descrito.
Algumas implementações são consideradas como especificação. São especificações informais e outras implementações devem ser compatíveis com esta, até os bugs, porque não há clareza quando é um bug e quando não é. Há prós e contras de se fazer isto.
Especificação para linguagem de programação.
Coloquei no GitHub para referência futura.