O início
É igual fazer qualquer software.
Uma linguagem nova surge da necessidade de resolver algum tipo problema específico ou geral de forma diferente do que se fazia antes. Foi assim quando se criou as primeiras linguagens de baixo nível (vários Assemblies) e depois com Fortran - considerada a primeira linguagem de alto nível - e então linguagens que foram usando ou adicionando novos paradigmas e estilos de código, atendendo necessidades que antes não eram contempladas pelas linguagens anteriores.
Claro que é possível criar uma linguagem sem inovar, sem atender uma necessidade não atendida antes. Pode-se criar uma só como exercício ou outro motivo.
Criar uma linguagem de programação é juntar um monte de ideias e regras e formalizar tudo, em maior ou menor grau. Uma linguagem é algo conceitual, é abstrata.
Filosofia
Obviamente durante a criação da linguagem tem uma série de decisões que deve-se tomar que vão além da gramática ou que vão influenciar a gramática (ver abaixo sobre o que é). Por exemplo:
- que paradigma(s) a linguagem adotará
- modelo de tipagem e de gerenciamento de memória
- critérios de eficiência de execução e tradução do código
- usabilidade, simplicidade, legibilidade, manutibilidade
- confiabilidade, precisão, robustez - o que é proibido (erro), permitido (alerta) e regular
- universalidade, portabilidade, forma de execução
- expressividade, estilo de sintaxe
- extensibilidade
- generalidade (ou o nicho específico)
- ortogonalidade, uniformidade, regularidade, consistência
- facilidade de implementação e ambientação
- como tratará situações específicas (manipulação de erros, facilidades para integração de ferramentas como debug ou IDE, por exemplo)
Até mesmo algumas coisas incomuns podem ser decididas e/ou especificadas. Outras, é melhor deixar em aberto, a linguagem não precisa exigir que tudo seja especificado e deixar que a implementação tenha uma certa liberdade.
Por isso antes de começar especificar a gramática costuma-se definir uma "visão", uma filosofia para a linguagem. São poucos itens que vão guiar as decisões, principalmente quando houver conflitos entre uma decisão e outra.
Pense que você está criando um produto, ou mesmo uma empresa. Precisa ter um "norte" para saber onde quer chegar, qual o resultado esperado, o que, em linhas gerais, pode ou não pode fazer quando surgir um obstáculo ou uma oportunidade. Quais são os "valores" da linguagem. Python tem isso formalmente, C++ também (provavelmente o mais bem definido, e seguido desde que existe, de todas linguagens).
Claro que se for geral demais, no fundo encaixa qualquer coisa. E se não for pra seguir, melhor não fazer. Se fizer e for rígido demais, a linguagem certamente será ruim.
Gramática
Como é uma linguagem ela precisa de uma gramática. Ou seja, precisa de um conjunto de regras para uso das palavras (incluso aí como essas são escritas). É comum que essas regras sejam escritas em BNF ou alguma variação dessa notação (curiosamente BNF não deixa de ser uma linguagem). Um exemplo da linguagem C. Gramática do JavaScript. Existe uma pergunta no SO com várias outras.
Essas regras são sintáticas e semânticas.
Existem alguns softwares que ajudam montar sua gramática, testá-la se tudo se encaixa como devido, e até mesmo gerar uma base de código para o compilador. Exemplos: YACC/Bison, ANTLR, GOLD, Coco/R, Flex, etc. Eles não fazem milagres. Se não usar um software desses, tem que fazer na mão, como em tudo na computação. Testar sem ajuda é tedioso e indutor de erros no processo.
Durante a criação da gramática é provável que mude muita coisa que se tinha ideia inicial. Algumas coisas não funcionam bem com outras como se costuma imaginar inicialmente. Depende da ortogonalidade.
Sempre vejo questionamentos sobre porque uma linguagem não permite isso ou aquilo. Quem é leigo no assunto acha que criaram a linguagem de um jeito errado. Muitas vezes há uma dificuldade ter tudo na mesma linguagem, as características não se encaixam. Outras apenas não se encaixam no objetivo traçado. E outras são erros mesmo :). Já quem não é programador nem consegue pensar nesse questionamento.
E depois?
Algumas regras, além da gramática, de como a implementação da linguagem podem ser especificadas e aí todo compilador/interpretador deve segui-las.
Depois de definir a linguagem, normalmente vem a definição de uma biblioteca padrão que toda implementação deve ter.
Com a linguagem especificada, é possível escrever um compilador para ela. É a implementação da linguagem. Aqui ela começa ficar concreta.
Obviamente outras ferramentas para auxiliá-la podem ser úteis, mas não obrigatórias.
Criadores de linguagens de uso geral adoram reescrever o compilador nela própria, assim que possível, serve até como marketing, isto chama-se bootstrapping.
Testes
Com a especificação fica fácil usar TDD (nunca vi fazerem :D). Um compilador é um projeto que esta metodologia cai muito bem, mas não obrigatória. Pelo menos testes de unidade devem ser feitos. Os testes devem sempre corresponder à especificação. Em alguns casos onde a especificação não seja formalizada, os testes servem como especificação.
Informações adicionais
C++
C++ é uma evolução do C. Basicamente toda linguagem é evolução de outras. Ela sempre agrega ou tira características para ter um conjunto de "funções" mais adequado para um determinado objetivo. Ela foi sendo definida por uma pessoa na AT&T, o mesmo local onde a linguagem C foi criada para escrever o Unix.
Seu objetivo era dar mais segurança e ser uma versão orientada a objetos do C. O Bjarne foi pensando no que precisava adicionar, usando um pouco Simula como base de ideias, especificava e ia analisando se as coisas se encaixavam, se algo poderia trazer problemas.
Existe uma filosofia básica para evolução da linguagem. Gramática do C++.
Coloquei no GitHub para referência futura.