REpresentational State Transfer (REST)-- the name used to refer to how the web works as-is, and why it works at the scale it is. Also known as the REST Architectural Style.
The web, or a web service in particular, is said to be RESTful if it follows the REST Architectural Style.
(If I'm not on a mistake, there is a new location for the RESTwiki)
REST is about using URIs to identify resources, using a small set of uniform actions (like, but not restricted to, HTTP's GET, PUT, POST, DELETE) to modify those resources, and transferring those resources using a representation of the resource.
For example, REST differs from RemoteProcedureCalls (RPCs) in that RPCs do not identify resources using a URI, they encourage a large number of actions (methods) to be performed, and they are more about passing parameters to those actions than about transferring state. See RestAndRpc.