Actually, Zarqawi didn't start calling his group al-Qaeda in Iraq until October 2004. But, his association with bin Laden goes back to 1989, when he was a jihadist in Afghanistan. He returned to his native Jordan and was imprisoned there in 1992 for oppositionist activities. Zarqawi tried to pulled off his first bombing in 1999 in Amman shortly after he was released. This is where his history gets interesting:
Upon his release from prison in 1999, Zarqawi was involved in an attempt to blow up the Radisson SAS Hotel in Amman, Jordan where many Israeli and American tourists lodged. He fled Jordan and travelled to Peshawar, Pakistan, near the Afghanistan border. In Afghanistan, Zarqawi established a militant training camp near Herat. According to the Bush administration, the training camp specialized in poisons and explosives.
Jordanian and European intelligence agencies claim that Zarqawi formed the group Jund al-Sham in 1999 with $200,000 of startup money from Osama bin Laden. The group originally consisted of 150 members. It was infiltrated by members of Jordanian intelligence and scattered by Operation Enduring Freedom . . .
Sometime in 2001, Zarqawi was arrested in Jordan but was soon released. http://en.wikipedia.org/wiki/Abu_Musab_al-ZarqawiThat certainly raises the question why Zarqawi, who had been imprisoned for seven years for mere plottings against King Hussein, was quickly released after he was rearrested, particularly since he had been at the center of a bomb plot, and had been close to Osama bin Laden at the time that al-Qaeda was at the top of the western intelligence wanted list. There's only one explanation that really makes sense for this. At the time, at least, he was a double-agent of some kind, probably for Jordanian intelligence and possibly also for the CIA. Recently, formed head of the CIA's UBL counter-terrorism unit, Michael Schauer, said that the U.S. had Zarqawi in its sites for at least a year before the invasion of Iraq, but the Bush Administration declined to take him out.
So many of the major figures in UBL's organization share this same characteristic.