I have implemented a REST API before and I really liked it. In general when you implement REST over SOAP, your client/server is more orthogonal meaning that you can a lot more freely change the server without affecting your client(s). This orthogonality is due to using a more abstract and already well defined communication via HTTP verbs. Also, the use of hyperlinks embedded in your REST responses make it easier to extend and grow your API relatively pain free. Clients are supposed to follow these embedded links to get to new resources like a human would follow links on a webpage to 'drill down' for more information.
With that said, I had some coworkers who were told they had to use SOAP and they complained about it all the time. So I went into researching the two a bit more in detail.
In general what I found is that REST is well suited for highly distributed applications, when you have hundreds, thousands or millions of clients. One reason is the above mentioned orthogonality, another is caching that you get for free since you are using HTTP.
SOAP might be the quicker way to go when you need a smaller API for a client or two quickly and you are not too worried about scalability. It might also fit you better if you do not have an architecture that is structured around resources, because it might take you some time to restructure your app to even be able to implement REST.