The word goes back to at least 1580 and at that time, and for a good while thereafter, the most prominent speakers of the English language lived in a kingdom on a small island in Northern Europe that they shared with only one other nation until the two joined into one. So for a good chunk of history and during the development of modern English, most travel between “home” and a foreign land required going over seas. Thus “overseas” took on a meaning of foreigness or awayness.