The haftorah of Shabbos Zachor opens with Shmuel's prophetic charge to Shaul to fulfill the mitzvah of utterly destroying Amalek. Thus the connection between the haftorah and Shabbos Zachor is obvious. Upon reflection, however, a second very important connection emerges as well.
Hakadosh Baruch Hu informs Shmuel that He has decided to punish Shaul's disobedience by stripping him of his kingship. Shmuel's reaction: "vayichar l'Shmuel vayiz'ak el Hashem kol halayla - Shmuel was very agitated and cried out to Hashem all night." Hakadosh Baruch Hu does not accept Shmuel's tefillah.
The following morning Shmuel forcefully, emphatically delivers Hakadosh Baruch Hu's message of reproach and punishment to Shaul. "Ya'an mo'asta es dvar Hashem v'yim'ascha mi'melech - because you have spurned the word of Hashem, He has spurned you as king." Shmuel does not betray the slightest trace of the previous night's advocacy for Shaul and profound agitation. His tefillah having been declined, Shmuel completely surrenders to the perfect, absolute moral will of Hakadosh Baruch Hu.
This provides the second connection between the haftorah and parshas Zachor. More than any other mitzvah, that of mechiyas Amalek calls for our surrender to the [at times] inscrutable will of Hakadosh Baruch Hu. The requirement to destroy Amalek mei'olel v'ad yoneik, from young child to suckling, is morally counter intuitive. And yet, like Shmuel, we unconditionally surrender to Hakadosh Baruch Hu. He is the exclusive source of morality[1], and His will (in the words of Rav Soloveitchik) is self-validating. We can, as Shmuel did, attempt through the merit of tefillah to have a decree rescinded. We can and should attempt to understand Hakadosh Baruch Hu's miztvos to the best of our ability[2]. It is, however, heretical hubris to question His morality.
"Ein shemo shaleim v'ein kis'o shaleim ad she'yimche shemo shel Amalek - Hakadosh Baruch Hu's name and throne are not whole until the name of Amalek is obliterated." Chazal link the establishment and revelation of Malchus Shomayim in the world [i.e., the ultimate redemption] to the destruction of Amalek. But, as illustrated by the haftorah, we will not destroy Amalek unless we first surrender to Hakadosh Baruch Hu's will and accept the mitzvah. Thus on a deeper level Chazal are teaching that the geulah will not come until we completely, unconditionally surrender to His will and moral judgment, bemehirah beyameinu amen.
[1] See Natural Law, TorahWeb Vayera 2002
[2] See Rambam end of Hilchos Me'elah