I read somewhere that William introduced Latin to the Anglo Saxons, but I'm not sure how true that is

Absolutely false. Latin had been in at least limited use in England since the country reconverted to Christianity in the 7th century. In England, as elsewhere, Latin remained the language of the church and of scholarship until the late middle ages. The monks of early medieval England were known for being articulate writers of formal Latin.

How did the warring sides communicate? Did they speak one another's respective languages? Was everybody speaking Latin? Were the Normans bilingual? Further, how did the Scandinavians and the Anglo Saxons communicate at Gate Fulford & Stamford Bridge (if there was any communication, that is - I've been taught that Harold surprised them at Stamford & launched an all out battle) - or was that made much easier by whatever remained of the language in England from the Viking conquests?

There's a lot to answer, and for a great deal of it I can do no better than admit we don't know. Our sources are not great for these kind of details; they're much more interested in the noble deeds (real or imagined) of whoever's sponsoring the chronicle. That said, England, Normandy, and Scandinavia were very well-connected places, both economically and politically; these peoples were not unfamiliar with one another. Remember, in the half-century prior to 1066, England had one Danish king (Cnut) and one half-Norman king (Edward the Confessor). I would be seriously surprised if William and Harald didn't have anyone along who could speak a bit of English, or vice versa.