REST (Representational State Transfer) is a style of Software Architecture for Hypermedia Systems (such as the World Wide Web). The term REST was first coined by Roy Fielding in his doctoral dissertation, fielding had a great deal to do with the specification of HTTP 1.0 and HTTP 1.1.
Representation State Transfer, Fielding describes "was intended to evoke an image of how a well designed web application behaves: a network of web pages, where the user processes through an application by selecting links (state transitions), results in the next page (representing the next state of an application) been transferred to the user and rendered for use".
The motiviation of REST was to capture the characteristics of the WEB which made it a success. Subsequently these characterstics are being used to guide the evolution of the Web. Rest is an architectural style and not a standard, you wont see a W3C REST specification or a REST Developers tool kit, you cannot bottle it up you can only understand it and design your web services like it.
Would this surfice to explain what REST is? If so I just have to find its relationship with HTTP and Web Services then I am done.
It beats around the bush rather, failing to say what it is about. REST is about treating a web application as collection of resources with links between them. A particular resource may have many representations (determined by HTTP content negotiation) and will support some subset of HTTP verbs applied to it (particularly GET, HEAD and OPTIONS of course, but also often PUT, POST and DELETE too). Idempotency of operations is an important thing to consider, and it should also be noted that the operations (particularly the idempotent PUT and the non-idempotent POST) do not necessarily map to creating and updating directly.
The representations transferred should be self-describing (in some sense) so HTML and XML are good, but there's no reason for representations being transferred in either direction to be those. Clients should not have to guess the URLs of resources.