O que é a assinatura de um método?

A assinatura é o jeito de identificar um método de forma única. Em linguagens onde vários métodos podem ter o mesmo nome, você precisa ter uma outra forma de evitar a ambiguidade. O compilador precisa saber qual dos métodos com mesmo nome você está chamando. Então você precisa se valer de informações extras disponíveis no método para tomar uma decisão. O mais comum é analisar os parâmetros. Se todos os parâmetros forem iguais, você tem o mesmo método, se apenas um desses parâmetros for diferente, você tem um método diferente. É possível que o retorno e outras informações possam ser analisadas também, mas isto não é comum já que podem trazer alguns problemas. Por igual entenda que a ordem também é importante.

Java é uma das linguagens que foram pelo caminho seguro de analisar só os parâmetros. Isto é comum acontecer. C# também foi por este caminho. C++ optou por utilizar o tipo do retorno também em algumas situações.

Em tese seria possível utilizar qualquer informação disponível, até o nome do parâmetro. Em geral isto seria uma má ideia, mas nada impede que uma linguagem utilize. É ela quem vai determinar o que é bom ou não para ela. Java e C# provavelmente se valeram dos problemas encontrados na utilização em C++ para evitar tanta flexibilidade.

Vejamos exemplos em Java (quase todos funcionam bem em C# também):

int FazAlgumaCoisa() { // faz alguma coisa aqui }

int FazAlgumacoisa(int valor) { // faz alguma coisa aqui }

Estes métodos têm o mesmo nome mas são diferentes, eles provavelmente executam alguma coisa (pelo menos) ligeiramente diferente (embora isto não seja obrigatório, apenas seria esquisito fazer exatamente o mesmo), mas não muito diferente, afinal, se isto ocorresse, não justificaria o mesmo nome. Há uma chance razoável do primeiro apenas chamar o segundo passando um parâmetro default (mas não precisa ser assim). Ex.:

int FazAlgumaCoisa() { FazAlgumaCoisa( 0 ); }

E agora vejas estes métodos:

int FazAlgumaCoisa(int valor1) { // faz alguma coisa aqui }

int FazAlgumaCoisa(int valor2) { // faz alguma coisa aqui }

Eles possuem a mesma assinatura ou não?

Possuem! Você teria um conflito se declarasse ambos. A análise só considera o tipo dos parâmetros, não seu nome.

Mas eu só coloquei a declaração dos métodos, não mostrei a declaração das classes. Eu considerei que estes métodos são da mesma classe. Isto quer dizer que você pode ter métodos que aparentam ter a mesma assinatura, mas no fundo a assinatura é diferente. Veja:

int FazAlgumaCoisa() { // faz alguma coisa aqui }

int FazAlgumaCoisa() { // faz alguma coisa aqui }

Isto é possível? Bem, é se os métodos pertencerem a classes diferentes:

class Exemplo1 {
    int FazAlgumaCoisa() { // faz alguma coisa aqui }
}
class Exemplo2 {
    int FazAlgumaCoisa() { // faz alguma coisa aqui }
}

Desta forma é válido. O que muita gente não entende é que métodos de instância possuem um parâmetro implícito (escondido). Podemos chamar ele de this. No fundo, por baixo dos panos, estas classes são montadas assim:

class Exemplo1 {
    int FazAlgumaCoisa(Exemplo1 this) { // faz alguma coisa aqui }
}
class Exemplo2 {
    int FazAlgumaCoisa(Exemplo2 this) { // faz alguma coisa aqui }
}

percebeu que a assinatura é diferente? Se usarmos o método que tinha um int como parâmetro explícito ficaria assim:

class Exemplo1 {
    int FazAlgumaCoisa(Exemplo1 this, int valor) { // faz alguma coisa aqui }
}
class Exemplo2 {
    int FazAlgumaCoisa(Exemplo2 this, int valor) { // faz alguma coisa aqui }
}

Coloquei no GitHub para referência futura.

Algumas pessoas vão falar no número de parâmetros do método. Mas é óbvio que se o número de parâmetros for diferente os tipos são diferentes, afinal leva-se em consideração todos os tipos, então no mínimo você estaria comparando um tipo determinado com nada, o que claramente é algo diferente. É óbvio que xxx(int, int) é diferente de xxx(int, int, int).

Lembrando que string, int é diferente de int, string. A ordem tem relevância.

Outros elementos podem fazer diferença na assinatura dependendo da linguagem.

Veja a especificação da linguagem Java (a pergunta original falava em Java).

A especificação do C# mais atual pode ser encontrada para download ou acesso direto (versão mais antiga). Em sua resposta o dcastro citou as partes mais relevantes dela.

A especificação do C++ deve ser comprada. Um rascunho está disponível gratuitamente.