I want to program some sort of notification system. What would be the be the best way to achieve this?
Like you said, it depends on message priority.
If notifications are made upon the visitor performing an action, it would be easy to tie in session-based notifications.
If notifications are made upon other users performing an action (e.g. "John made an edit to this page. Click here to view."), you could use long-polling AJAX to wait for a notification.