Difference between a SOAP message and a WSDL?

A SOAP message is an XML document which is used to transmit your data. WSDL is an XML document which describes how to connect and make requests to your web service.

Basically SOAP messages are the data you transmit, WSDL tells you what you can do and how to make the calls.

A quick search in Google will yield many sources for additional reading (previous book link now dead, to combat this will put any new recommendations in comments)

Just noting your specific questions:

Are all SOAP messages WSDL's? No, they are not the same thing at all.

Is SOAP a protocol that accepts its own 'SOAP messages' or 'WSDL's? No - reading required as this is far off.

If they are different, then when should I use SOAP messages and when should I use WSDL's? Soap is structure you apply to your message/data for transfer. WSDLs are used only to determine how to make calls to the service in the first place. Often this is a one time thing when you first add code to make a call to a particular webservice.

A SOAP document is sent per request. Say we were a book store, and had a remote server we queried to learn the current price of a particular book. Say we needed to pass the Book's title, number of pages and ISBN number to the server.

Whenever we wanted to know the price, we'd send a unique SOAP message. It'd look something like this;

<SOAP-ENV:Envelope
  xmlns:SOAP-ENV="http://schemas.xmlsoap.org/soap/envelope/"
  SOAP-ENV:encodingStyle="http://schemas.xmlsoap.org/soap/encoding/">
  <SOAP-ENV:Body>
    <m:GetBookPrice xmlns:m="http://namespaces.my-example-book-info.com">
      <ISBN>978-0451524935</ISBN>
      <Title>1984</Title>
      <NumPages>328</NumPages>
    </m:GetBookPrice>
  </SOAP-ENV:Body>
</SOAP-ENV:Envelope> 

And we expect to get a SOAP response message back like;

<SOAP-ENV:Envelope
  xmlns:SOAP-ENV="http://schemas.xmlsoap.org/soap/envelope/"
  SOAP-ENV:encodingStyle="http://schemas.xmlsoap.org/soap/encoding/">
  <SOAP-ENV:Body>
    <m:GetBookPriceResponse xmlns:m="http://namespaces.my-example-book-info.com">
      <CurrentPrice>8.99</CurrentPrice>
      <Currency>USD</Currency>
    </m:GetBookPriceResponse>
  </SOAP-ENV:Body>
</SOAP-ENV:Envelope>

The WSDL then describes how to handle/process this message when a server receives it. In our case, it describes what types the Title, NumPages & ISBN would be, whether we should expect a response from the GetBookPrice message and what that response should look like.

The types would look like this;

<wsdl:types>

  <!-- all type declarations are in a chunk of xsd -->
  <xsd:schema targetNamespace="http://namespaces.my-example-book-info.com"
    xmlns:xsd="http://www.w3.org/1999/XMLSchema">

    <xsd:element name="GetBookPrice">
      <xsd:complexType>
        <xsd:sequence>
          <xsd:element name="ISBN" type="string"/>
          <xsd:element name="Title" type="string"/>
          <xsd:element name="NumPages" type="integer"/>
        </xsd:sequence>
      </xsd:complexType>
    </xsd:element>

    <xsd:element name="GetBookPriceResponse">
      <xsd:complexType>
        <xsd:sequence>
          <xsd:element name="CurrentPrice" type="decimal" />
          <xsd:element name="Currency" type="string" />
        </xsd:sequence>
      </xsd:complexType>
    </xsd:element>

  </xsd:schema>
</wsdl:types>

But the WSDL also contains more information, about which functions link together to make operations, and what operations are avaliable in the service, and whereabouts on a network you can access the service/operations.

See also W3 Annotated WSDL Examples