Should I log messages to stderr or stdout?

Regular output (the actual result of running the program) should go on stdout, things like you mentioned (e.g. diagnostic, notice, warning, error) on stderr.

If there is no "regular output", I would say that it doesn't really matter which one you choose. You could argue that the logging is the only output, so that should go to stdout. Or you could argue that it is still "exceptional information" which should go to stderr.

Do you write something else to stdout? If the answer is Yes then it would be quite hard for someone to distinguish between normal flow and errors in the middle of the file that was used to redirect from stdout.

What if stdout will be used as input for another program? Will it be able to parse this debug information? In this case it would be good to write only critical errors to stderr. If you need to write something else you may consider to write to additional log file.