O que "imutável" realmente significa?

Nessa pergunta que fiz a respeito de tipos valor e tipos referência em C#, foi citado na resposta aceita que instâncias de structs devem ser objetos imutáveis. Lendo no wikipedia confirmei que um objeto imutável não deveria ter seu estado modificado depois de criado. Mas isso é confuso, porque afinal, se eu declaro uma variável seja de um tipo struct ou um tipo classe, eu posso modificar seu valor a qualquer momento, ou então ela seria uma constante.

Uma assinatura do método/função comum ou construtor é composta por seu nome + quantidade de parâmetros + tipo dos parâmetros?