The best follow-up question to ask someone is: "What level on the Richardson Maturity Model is your RESTful API?" If they can't answer that, they're probably using the term RESTful to describe something else.
Richardson Maturity Model:
Level Zero Service - URI API. Usually just POST. SOAP, XML-RPC, POX.
Level One Service - URI Tunneling via URI Templates. GET/POST.
Level Two Service - CRUD (POST, GET, PUT, DELETE). Amazon S3.
Level Three Service - "Hypermedia as the Engine of Application State" (HATEOAS).
HATEOAS is the most complicated. Imagine you're browsing the internet. You go to a webpage, and it loads with lots of text, links, images, and videos. You can interact with it, click on links, watch videos, submit a form, and go elsewhere. You have no idea what appeared on the webpage until after you visited it, and the next time you visit it might change entirely. The link might become broken and you get 404'ed, or you need a username/password otherwise you get 401'ed. HATEOAS is similar to that, but instead of a "person" browsing a "website", it's "client software" browsing "XML/URIs/Resources" received from a server API.
REST is not easy to understand or explain, as it entails learning about many different concepts, ideas, and custom-building something based on them. This is probably why there's no single-sentence which easily describes REST. Saying that something is RESTful is like saying something is Drivable. You can drive a car, truck, motorcycle, bicycle, or boat, but they're all very different from one another. There are similar concepts between them, like accelerating, steering, breaking, but how they do each of those things is very different.
A good book I recommend is "REST in Practice" by Jim Webber, Savas Parastatidis, and Ian Robinson (http://www.amazon.com/REST-Practice-Hypermedia-Systems-Archi... or http://shop.oreilly.com/product/9780596805838.do). That helped me grasp what REST means.
Get dozens of book recommendations delivered straight to your inbox every Thursday.