As far as I'm concerned, pragmatically, its using the HTTP verbs to operate on resources, named according to a certain URL convention (e.g. users/<userid>), when the semantics of the verbs are followed.
E.g. GET shouldn't change resource state; POST should be used to create a new resource (which the server will typically name); PUT should be used to update an existing named resource, etc.
What format of data sent using these verbs can vary - JSON is one popular format, and what I'd choose.
However, in practice, when people say their API is RESTful, it often just means 'you can access our API over HTTP'. Often you see everything implemented as GET requests - for better or worse.
And there are some pragmatic reasons for that - e.g. maybe devs decide they want to use JSONP to get around same origin restrictions; there's web developers out there who can only make GET requests, etc.