REST and DELETE?

There's something I'm not getting about REST.

We're supposed to use HTTP verbs like GET, PUT, POST and DELETE.

But we're also supposed to be avoiding server state, like sessions.

How can we have a stateless protocol (that is, a protocol in which all
state is saved in the client, using the REST hierarchy as a sort of state
machine), that supports a DELETE operation?

Are some HTTP verbs more RESTful than others?  It seems like PUT, POST and
DELETE are all about storing state on the server.

Thanks!