REST ou RESTFUL (Definição)

########################### Retirado de um post do Stack Overflow ###########################

Só faz sentido saber o que é REST, já que RESTful é apenas a capacidade de fazer REST, ou seja, é uma questão gramatical.

A Representational State Transfer (REST), em português Transferência de Estado Representacional, é uma abstração da arquitetura da World Wide Web, mais precisamente, é um estilo arquitetural que consiste de um conjunto coordenado de restrições arquiteturais aplicadas a componentes, conectores e elementos de dados dentro de um sistema de hipermídia distribuído.

O REST ignora os detalhes da implementação de componente e a sintaxe de protocolo com o objetivo de focar nos papéis dos componentes, nas restrições sobre sua interação com outros componentes e na sua interpretação de elementos de dados significantes.

Ele foi definido oficialmente pela W3C.

Fonte: Wikipedia (em inglês)

Ele é frequentemente aplicado à web services fornecendo APIs para acesso a um serviço qualquer na web. Ele usa integralmente as mensagens HTTP para se comunicar através do que já é definido no protocolo sem precisar "inventar" novos protocolos específicos para aquela aplicação.

Você trabalha essencialmente com componentes, conectores e dados.

Ele usa o protocolo HTTP (verbos, accept headers, códigos de estado HTTP, Content-Type) de forma explícita e representativa para se comunicar. URIs são usados para expor a estrutura do serviço. Utiliza uma notação comum para transferência de dados como XML ou JSON.
Não possui estado entre essas comunicações, ou seja, cada comunicação é independente e uniforme (padronizada) precisando passar toda informação necessária.
Ele deve facilitar o cache de conteúdo no cliente.
Deve ter clara definição do que faz parte do cliente e do servidor. O cliente não precisa saber como o servidor armazena dados, por exemplo. Assim cada implementação não depende da outra e se torna mais escalável.
Permite o uso em camadas também facilitando a escalabilidade, confiabilidade e segurança.
Frequentemente é criado com alguma forma de extensibilidade.
Falhando em um dos cinco primeiros itens, a arquitetura não pode ser classificada formalmente como RESTful. Mas nem todo mundo se apega ao formalismo.

Exemplo:

http://example.com/apagar/produto/1234
significa que você está pedindo para apagar o produto de ID 1234.

Há quem diga que isto está errado e já que a ênfase é em cima dos recursos e não das operações. Deveria usar assim:

http://example.com/produto/1234 (utilizando o verbo DELETE)
Convenhamos que isto pode servir para CRUD, mas existem tantas variações do que precisa ser feito que não é possível representar tudo só com os verbos HTTP. Ok, é possível fazer tudo parecer CRUD, mas talvez exija informações adicionais em nome do formalismo.

Tudo isto é pensado para proporcionar melhor performance, escalabilidade, simplicidade, flexibilidade, visibilidade, portabilidade e confiabilidade.

Cada um define como quiser sua API, ao contrário de SOAP onde tudo é definido oficialmente.