REST vs SOAP is not the right question to ask.
REST, unlike SOAP is not a protocol.
REST is an architectural style and a design for network-based software architectures.
REST concepts are referred to as resources. A representation of a resource must be stateless. It is represented via some media type. Some examples of media types include XML, JSON, and RDF. Resources are manipulated by components. Components request and manipulate resources via a standard uniform interface. In the case of HTTP, this interface consists of standard HTTP ops e.g. GET, PUT, POST, DELETE.
@Abdulaziz's question does illuminate the fact that REST and HTTP are often used in tandem. This is primarily due to the simplicity of HTTP and its very natural mapping to RESTful principles.
Fundamental REST Principles
Client-Server Communication
Client-server architectures have a very distinct separation of concerns. All applications built in the RESTful style must also be client-server in principle.
Stateless
Each client request to the server requires that its state be fully represented. The server must be able to completely understand the client request without using any server context or server session state. It follows that all state must be kept on the client.
Cacheable
Cache constraints may be used, thus enabling response data to be marked as cacheable or not-cacheable. Any data marked as cacheable may be reused as the response to the same subsequent request.
Uniform Interface
All components must interact through a single uniform interface. Because all component interaction occurs via this interface, interaction with different services is very simple. The interface is the same! This also means that implementation changes can be made in isolation. Such changes, will not affect fundamental component interaction because the uniform interface is always unchanged. One disadvantage is that you are stuck with the interface. If an optimization could be provided to a specific service by changing the interface, you are out of luck as REST prohibits this. On the bright side, however, REST is optimized for the web, hence incredible popularity of REST over HTTP!
The above concepts represent defining characteristics of REST and differentiate the REST architecture from other architectures like web services. It is useful to note that a REST service is a web service, but a web service is not necessarily a REST service.
See this blog post on REST Design PrincipalsPrinciples for more details on REST and the above stated bullets.
EDIT: update content based on comments
