REST is an architectural style for building web services.
REST is built on top of HTTP. Your web service exposes Resources in the form of URIs. Your service allows clients to act upon your service using the standard HTTP verbs (GET=read the resource, POST=create the resource, PUT=update the resource, DELETE=delete the resource).
REST has gained significant momentum in the past few years due largely to (a) Its simplicity over other styles like SOAP. (b) The ubiquity of HTTP. Because HTTP is a time-tested standard, most languages have build-in or 3rd-party HTTP support. You cannot say the same thing about SOAP.
Because REST is a style and not a strict protocol/specification, there is lots of room for interpretation. Many public services that call themselves "REST" do not follow the style to the letter.