É uma string que define um padrão de busca. É um algoritmo. Podemos dizer que ela é uma linguagem para localização de padrões em texto.
Ela não é uma linguagem de programação, mas sua implementação está disponível em praticamente todas as bibliotecas padrões das linguagens de programação, ou por biblioteca de terceiros.
Algumas implementações são bem simples tendo apenas uma função, outras possuem diversas classes com diversas utilidades. Algumas linguagens preferiram embuti-la como uma construção. Existem variações de linguagem. Algumas mais mais completas, outras só com os códigos principais.
Podemos dizer que é um padrão de projeto, mas como ela é tão antiga, tão pervasiva, que ninguém nem define desta forma.
É uma forma de obter a localização de padrões de texto dentro de outros textos através de uma sequência de códigos que indiquem como deve ser composto esse padrão para encaixar no que se procura. Outras formas podem ser tediosas, precisarem de códigos maiores e o programador pode errar mais facilmente, ainda que os programadores inexperientes possam criar diversos falsos positivos se não testam adequadamente.
É comum ter funções, que além de localizar faz a mudança de um padrão por algum outro texto.
Normalmente é abreviada como regex ou regexp.
Particularmente acho ilegível e e prefiro funções que indicam de forma mais "por extenso" o que deseja (algumas linguagens possuem bibliotecas para isso) e ela frequentemente é muito mais lenta que fazer um laço na mão (alguns casos podepodem ser bem complicado, mas se tiver funções que ajudem não não é ruim). Eu respeitaria mais se fosse uma variação de ABNF.