This line is printed by the shell. Different shells implement looking for mail in slightly different ways, but unless can count on people to configure their shells to your liking (and possibly pick a different shell), you need to send them mail.
Good shells designed for interactive use have a way to run arbitrary commands before displaying a prompt, in addition to the built-in mail notification. You can have your users cat a file there, or do something more complicated. For zsh users, put this in ~/.zshrc:
precmd () {
if [[ /etc/sysadmin-message -nt ~/.sysadmin-message-timestamp ]]; then
cat /etc/sysadmin-message
touch ~/.sysadmin-message-timestamp
fi
}
For bash users, put this in ~/.bashrc:
PROMPT_COMMAND='
if [[ /etc/sysadmin-message -nt ~/.sysadmin-message-timestamp ]]; then
cat /etc/sysadmin-message
touch ~/.sysadmin-message-timestamp
fi
'