REST - Transferencia de Estado Representativa
REST significa básicamente que cada URL única es una representación de algún objeto. Puedes obtener el contenido de ese objeto usando HTTP GET, para borrarlo, entonces podrías usar un POST, PUT, o DELETE para modificar el objeto (en la práctica la mayoría de los servicios usan un POST para esto).
SOAP - Protocolo simple de acceso a objetos
SOAP se utiliza sobre todo en las aplicaciones empresariales para integrar un gran número de tipos de aplicaciones y otra tendencia es la integración con sistemas heredados, etc. Google es consistente en la implementación de sus servicios web utilizando SOAP (excepto Blogger)
SOAP gana con GeoProcessing con ArcGIS Server +1 para Kirk