And, of course, a bit of more google search, and I arrived at the asnwer:
one needs to use the admin_notices hook:
add_action('admin_notices', create_function('', 'echo "<div class=\"error\">This is my error";')); //for errors (red background)
add_action('admin_notices', create_function('', 'echo "<div class=\"updated\">This is my error";')); //for other notifications (yellow background)