(Updated to include MSN response; updated again for the China thing.)
According to this CBC article, Yahoo, MSN, and AOL have all willingly handed over search records to the U.S. government (they claim that no personal information is included, but personal information can often be inferred from search URLs). Google said ‘no’, and is now taking the fight to court.
The request is unrelated to national security — instead, the government is gathering background evidence to defend an anti-porn law in court.
Update #2: And now, Google has agreed to censor search results for China. It guess this pulls Google back down to a karmic break even: defender of privacy rights in North America, but anti-free-speech collaborator in Asia.