How complicated is security using REST ?
Is it just a matter of passing an authenticating token in the request ?
I think the short answer is "yes."
Clients need to send opaque IDs that the API knows how to authenticate so that it can enforce an authorization policy. If a client "hasSecureStorage" it might be able to store some sort of secret password (client credentials). Otherwise the token will be exposed, so it cannot be trusted on its own. This usually means adding a time dimension, a TTL for the token, which theoretically limits the exposure if compromised. Transport Layer Security (TLS) should probably be a given for any apps that care about the security of the data or the trustworthiness of the identity represented by the client request's access token.
Architecturally, I like OAuth 2.0's idea of a centralized third party (Authorization Server) that the client and server both talk to manage some level of authentication, authorization, and client state. This helps keep each REST API node stateless (with respect to client state) and pushes that to a service that is built with a special purpose to manage it centrally (today, we might call this Facebook ).
The WRML application framework borrows this idea of leveraging a set of core REST-based services, like OAuth 2's AuthZ server, as key dependencies for the modern client-server apps. In my mind, this is true web service-oriented architecture with applications built from services that are treated like native data structures (and algorithms).