Have a look at the Message Stack, these are the basic components and dependencies of it:
Some more details about the Message-related modules (=quotes are from the module's project page):
Message:
The Message module is the core of the message stack. It enables logging and displaying system events in a number of different use cases. Events that are recorded over time are sometimes call activity streams. Exportable messages subtypes can be created for different use cases with custom fields and display (view) modes.
Message Notify.
This module provides a method for sending a message via a notifier plugin. Message Notify comes with plugins for email and SMS and may be extended to other transport mechanisms as required.
Message Subscribe.
With this module, users who subscribe to content will be notified when events occur that involve that content. The module leverages the Flag module, which provides a subscribe functionality to users.
Quite a few popular Drupal distributions already adopted to this Message Stack, Open Atrium is one of them.
If you'd rather look at an existing module as an example, then checkout the 7.x-4.x version of the Answers module (disclosure: I'm a co-maintainer) and its Answers Notification sub-module. This sub-module allows logged in users to subscribe to selected questions, so that they receive notifications (using the Message Stack) when Questions receive Answers.