Macbeth's words, "So foul and fair a day I have not seen," are significant because they ironically echo the witches' first incantation, "Fair is foul and foul is fair."
Both statements are paradoxes (seemingly contradictory truth) and dualities: how can fair be foul (its opposite), and vice-versa? How can a day be both fair and foul?
It has been a foul day insomuch as Macbeth has disemboweled and beheaded Macdonwald in the battle against Norway. At the same time, it has been a fair day in that Scotland has won the battle. It is a foul day that the old Thane of Cawdor is killed for treason; it is a fair day that Macbeth is promoted to his title. It will be a fair day when Macbeth becomes King and a foul day when he murders to do so.
In Macbeth, Shakespeare means to blur the lines of natural order, of what is fair (good, beautiful) and of what is foul (evil, ugly). It's not long before the natural order is topsy-turvy, and Shakespeare begs the question: who speaks truth? The natural (pre-King Macbeth), the unnatural (King Macbeth), or the supernatural (witches)?
Macbeth does not appear until the third scene of the first act in the play. His first words are
"So foul and fair a day I have not seen" (I,iii,38).
Macbeth speaks these words to Banquo, as they come upon the three witches. His words are significant because they clearly state one of the central motifs in the play - the idea of duplicity, that things are not what they seem. This motif is evident in the cryptic words the witches address towards Banquo in this scene. They greet him, saying,
"Lesser than Macbeth, and greater.
Not so happy, yet much happier.
Thous shalt get kings, though thou be none" (I,iii,65-67).
Banquo is subordinate to Macbeth, but in the end, the witches predict that he will be greater than him, and that Banquo's sons shall be kings. Things are not what they seem.
The motif carries over to the witches, whom Banquo suspects are women but who have "beards". Lady Macbeth later evidences this dichotomy in another way; she appears to be a upright and devoted woman, but in reality she is ruthless and ambitious, and wishes to be unsexed so that any soft part of her nature will be eradicated and she will have the "manly" strength to carry out her evil designs. Macbeth and Lady Macbeth welcome King Duncan cordially into their home, all the while plotting to kill him. When guilt drives Lady Macbeth to the point of insanity, she sees blood where there is none, and Macbeth thinks that he is safe from the last prophesies because he believes it impossible that the forest at Birnam will march to Dunsinane, and because the witches have told him that no man born of woman can harm him. Contrary to what seems logical, the forest does indeed come to the castle when the soldiers, camoflaged by branches from the woods, launch an assault, and Macduff, who was not "born of woman" because he was untimely ripped from his mother's womb, confronts Macbeth and kills him. Things throughout the play are simultaneously "fair and foul"; nothing is as it seems.