QUESTION: How do I provide a REST API for deleting resources in the system (e.g., a record from a database)? I was told that using a simple GET API, or even POST, is inappropriate, but I don't know why.
ANSWER: There's a well-known story about a company that had its entire database wiped out by Google. Why? Because they had a "delete" link on every web page, and Googlebot crawled all links it could find...
The lesson was quickly learned by the entire industry: do not expose deletion link, or more generally, state-changing links, as simple web links. And since a REST API is often described as a simple web URL, the convention was carried over.
In fact, if you never expose your REST action URLs as web links, you could use standard GET operations for deletion. However, it's not a good idea. On a conceptual level, a good REST design takes advantage of the various HTTP verbs, to prevent errors, confusion, or mistaken operations. And there's a very specific HTTP verb for deletion, namely DELETE.
See also item #5 in the page about REST Design Guidelines in this tutorial.