Show message at every page regardless page content
Why not to write it directly in the template? Or create a Block which you show in the header? or do you need to use the drupal_set_message() Message?

You can use "Drupal is initializing" event at Rules.