Britain's government has denied the memo of a conversation between Bush and Tony Blair, the British prime minister, included any suggestion of bombing the broadcaster, whose coverage of Iraq has angered US officials.
Civil servant David Keogh, 49, and Leo O'Connor, 42, who worked as a researcher for a parliament member, face charges under Britain's Official Secrets Act in the leaking of the memo.
At London's Old Bailey criminal court, Keogh pleaded not guilty to two counts of making a damaging disclosure and O'Connor pleaded not guilty to one count of the same charge.
Both men were released on bail.
Their trial is expected to start on October 9 and last up to three weeks.
The Daily Mirror newspaper said the memo came from Blair's Downing Street office and related to a conversation between the two leaders at the White House on April 16, 2004.
In its report in November, the Mirror quoted an unnamed government official as suggesting Bush's threat was a joke, but cited another unidentified source saying Bush was serious.
It said Blair talked Bush out of the idea.
Aljazeera's coverage of the war
in Iraq has angered US officials
The White House has described the Mirror report as "outlandish" and Blair's spokesman said in January that "the memo does not refer to bombing the Al Jazeera station in Qatar".
The Mirror journalist who broke the story has suggested Bush may have used another military term in the discussion.
Al Jazeera has repeatedly denied US accusations that it sides with insurgents in Iraq.
The US has criticised the station for what it sees as inflammatory reports and for broadcasting statements by al Qaeda and Iraqi insurgents.
The Mirror said the memo came from Blair's Downing Street office and turned up in May 2004 at the local office of Tony Clarke, then a member of parliament for Blair's Labour party, who had employed O'Connor as a researcher.
Clarke handed the document back to the government. Another Labour lawmaker, Peter Kilfoyle has said Clarke briefed him on the memo and it had included a discussion of bombing Al Jazeera and of an attack on the Iraqi town of Falluja.
Ayoub was killed in a US strike
on Al Jazeera's Baghdad bureau
The British government's top lawyer has warned media organisations they would be breaking the law if they published details of the leaked document.
In April 2003, Tariq Ayoub, an Al Jazeera journalist, was killed when the channel's Baghdad office was struck during a US bombing campaign. Nabil Khoury, a US State Department spokesman in Doha, said the strike was a mistake.
In November 2002, Al Jazeera's office in Kabul, Afghanistan, was destroyed by a US missile.
None of the crew was at the office at the time.
US officials said they believed the target was a terrorist site and did not know it was Al Jazeera's office.