Under the USA PATRIOT Act, keepers of records of any kind can be prosecuted if they tell anyone that the government subpoenaed information related to terror investigations. This restriction is known as a gag order, and a subpoenas with a national-security-related gag order attached is known as a national security letter (NSL).
A warrant canary is a method of allowing the recipient of a gag order to inform the public of such receipt without violating the rule against specifically stating that one has been received.
The legality of warrant canaries has never been tested in court, so there is no reason to think that they are any more legal than simply announcing that one has received a subpoena-and-gag-order -- which may in fact be legal; see "Status".
It is unclear if this provision remains in effect: