REST web services are not nearly as formalized as their SOAP equivalent. A REST web service adheres to the principals laid out in Roy Fielding’s PhD Thesis. REST stands for Representational State Transition.
From a practical standpoint, I consider a REST web service to be an HTTP v1.1 call that uses a JSON or XML payload that adheres to the JAX-RS spec (yes, I realize this is a very Java-centric way of looking at things). No, I’m not to concerned about it at this point.