However, there are various passages in the beginning of the Parasha that indicate that Esav left long before Jacob came. For example in chapter 32:
|וַיִּשְׁלַח יַעֲקֹב מַלְאָכִים לְפָנָיו, אֶל-עֵשָׂו אָחִיו, אַרְצָה שֵׂעִיר, שְׂדֵה אֱדוֹם.||4 And Jacob sent messengers before him to Esau his brother unto the land of Seir, the field of Edom.|
Jacob when he is heading home, sends his messangers to Esav at Edom! In other words, Esav was no longer in Canaan when Jacob was heading home.
Very few of the classical commentators comment on this - Radak explains that Esav was in Edom, but had yet to settle there. Ibn-Ezra expalins that Edom is between Haran and Israel, and hence Jacob has to send the messangers to Esav. This explains why Jacob bothered to send messengers to Esav at all, but not why Esav had already left Canaan. Nahmanides (commentary on Gen. 36:6) explains that initially Esau moved to Edom with only a few of his people, leaving most of his family in Canaan. Later, he returned to Canaan to meet Jacob, who was coming back from Laban's home, and only afterward did he take the rest of his family to Edom. Hazkoni (Gen. 36:6) similarly explains that until this point Esav lived in both places, and now he decided to give up any rights to Canaan.
These explanations are all possible, though somewhat unsatisfactory. Harav Goren gives a different explanation. Esav left Canaan long before Jacob returned, because Esav truely believed his father's blessings would come true (evidenced by his cry of anguish). Since Esav had no wish to be ruled by his brother, he got up and left before Jacob came back. The problem with this explanation is that the Torah specifically says Esav left because the land could not bare them both.