"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 (ignoring suspensions which set reputation to 1). Given that, it's up to the moderator to simply select "destroy" from the mod menu.