How do I add a new template to the catalog?

You can't just yet (Fall 2017), but this is one of the many things that we are looking at.

For now, however, there is a quick workaround: you can copy an existing message with one click to create a new one from it.

So you can sort of using existing messages as templates.