"Deleted" users have their display name denormalized, their account deleted, and all of their negatively-scored posts deleted (except on meta sites and open questions with one or more positively-scored answers). Anything not deleted is retained with their "ghost" user. This is primarily for scenarios like a user requesting their account be deleted, or multiple suspensions have not helped with a user's conduct.
"Destroyed" users have all that, but also have all of their posts and comments deleted. It is intended for things like spammers, where we just want them to be gone. A user must have less than 500 reputation in order to be destroyed. Given that, it's up to the moderator to simply select "destroy" from the mod menu.