What is the best way to return errors from a WCF service in a RESTful way?

With .net 4, throw a WebFaultException<T>(T errorDetail, HttpResponseCodecode)

Here you set your response type to another object type, which makes sense, and also you set the ResponseCode that you want.

The errorDetail must be serializable

http://blogs.msdn.com/b/endpoint/archive/2010/01/21/error-handling-in-wcf-webhttp-services-with-webfaultexception.aspx