MySQL “Statement may not be safe to log in statement format” warning

Question

What is the meaning of the following MySQL warning:

Statement may not be safe to log in statement format.

I have some tens of thousands of these statements every day in my mysqld.err file, and I'm not sure where should I begin my investigation.