There are two parts to this passive periphrastic, one adjectival and one a form of the verb to be. The adjectival form is the gerundive - note the "nd" before the ending. The ending is, in this case, feminine, nominative singular, to agree with the noun Carthago, which, like many place names, is feminine.
The agent, or in Cato's case, the person who would be doing the destroying, is expressed by a dative of agent.
Carthago____________Romae__________________ delenda est
Carthage (nom. sg. fem.) [by] Rome (dative case) destroyed (gerundive nom. sg. fem.) 'to be' (3rd sg. present)
Eventually, Cato got his way.
Here's another example: Marc Antony probably thought:
Cicero____________Octaviano__________________ delendus est
Cicero (nom. sg. masc.) [by] Octavianus (dative case) destroyed (gerundive nom. sg. masc.) 'to be' (3rd sg. present)