Drupal 7

To create a message type, navigate to /admin/structure/messages and click on "Add message type".

In the example below, a very basic message text is shown. Inserting tokens into message text field provides much greater utility. Note the undefined language field. The message module also supports multilingual sites. Note also the option to create another item in the message text field. This multivalue property of the message text can be used in conjunction with view modes to create render messages many different ways.

Once you have entered your message text, save the form.

The newly created message type is now listed. Here you can see a number of options for managing message types.

Click the "manage fields" link to attach custom fields to the message type. In the example below, an entity reference field has been added. When creating message instances this field will be used to store a relationship between the message and a target node entity.

Click the "manage display" link to see the message text field listed. When the message text field has multiple values, the message module splits each item (or "partial") into a separate partial display item.

Drupal 8

In Drupal 8 term 'Message types' was replaced by 'Message templates'.
To create new 'Message template' visit
/admin/structure/message
then click on 'Add message template' button.