The previous answers contain a lot of information, but I think there is a philosophical difference that hasn't been pointed out. SOAP was the answer to "how to we create a modern, object-oriented, platform and protocol independent successor to RPC?". REST developed from the question, "how to we take the insights that made HTTP so successful for the web, and use them for distributed computing?"
SOAP is a about giving you tools to make distributed programming look like ... programming. REST tries to impose a style to simplify distributed interfaces, so that distributed resources can refer to each other like distributed html pages can refer to each other. One way it does that is attempt to (mostly) restrict operations to "CRUD" on resources (create, read, update, delete).
REST is still young -- although it is oriented towards "human readable" services, it doesn't rule out introspection services, etc. or automatic creation of proxies. However, these have not been standardized (as I write). SOAP gives you these things, but (IMHO) gives you "only" these things, whereas the style imposed by REST is already encouraging the spread of web services because of its simplicity. I would myself encourage newbie service providers to choose REST unless there are specific SOAP-provided features they need to use.
In my opinion, then, if you are implementing a "greenfield" API, and don't know that much about possible clients, I would choose REST as the style it encourages tends to help make interfaces comprehensible, and easy to develop to. If you know a lot about client and server, and there are specific SOAP tools that will make life easy for both, then I wouldn't be religious about REST, though.