The Jews decreed foreign soil (i.e., dirt from Gentile lands) to be unclean.1
For it was taught, Yose ben Yoʿezer of Tzereida and Yose ben Yochanan of Yerushalaim decreed uncleanness concerning the land of the nations (i.e., Gentiles) and glass vessels.
דתניא יוסי בן יועזר איש צרידה ויוסי בן יוחנן איש ירושלים גזרו טומאה על ארץ העמים ועל כלי זכוכית
They assumed a possibility that the dirt came from a heathen grave, and it would thus transmit uncleanness to the Jew who came in contact with it. This notion is referred to as ספק עפר הבא מארץ העמים (safek afar ha-ba meʾeretz ha-ammim)—“doubt of the dust that comes from the land of the nations.”
Therefore, the Jew who came from or had contact with soil from a foreign land would shake it off.
John Lightfoot explains the significance of the Lord Jesus Christ’s command,2
Therefore that rite of shaking the dust off the feet, commanded the disciples, speaks thus much; “Wheresoever a city of Israel shall not receive you, when ye depart, shew, by shaking off the dust from your feet, that ye esteem that city, however a city of Israel, for a heathen, profane, impure city; and, as such, abhor it.”
1 Babylonian Talmud, Seder Moʿed, Tractate Shabbat, Chapter 1, Folio 14b, Gemara
2 Lightfoot, p. 186
Lightfoot, John. Horae Hebraicae et Talmudicae: Hebrew and Talmudical Exercitations. Trans. Gandell, Robert. Vol. 2. Oxford: UP of Oxford, 1859.