Had Morgoth heard about the coming of men and went looking for them on purpose or was he just wandering and happened upon them? Also how did Morgoth know the tongue of Men?
Melkor knew that Men would eventually arise
In those days, moreover, though the Valar knew indeed of the coming of Men that were to be, the Elves as yet naught of it; for Manwë had not revealed it to them. But Melkor spoke to them in secret of Mortal Men, seeing how the silence of the Valar might be twisted to evil. Little he knew yet concerning Men, for engrossed with his own thought in the Music he had paid small heed to the Third Theme of Ilúvatar; but now the whisper went among the Elves that Manwë held them captive, so that Men might come and supplant them in the kingdoms of Middle-earth, for the Valar saw that they might more easily sway this short-lived and weaker race, defrauding the Elves of the inheritance of Ilúvatar.
Although he was not as knowledgeable as the other Valar, preferring to spend his time defying Eru rather than listening to the Music, he still knew that humans would eventually come to be.
The Valar certainly believed that Morgoth might seek out humans:
These things the Valar did, recalling in their twilight the darkness of the lands of Arda; and they resolved now to illumine Middle-earth and with light to hinder the deeds of Melkor. For they remembered the Avari that remained by the waters of their awakening, and they did not utterly forsake the Noldor in exile; and Manwë knew also that the hour of the coming of Men was drawn nigh. And it is said indeed that, even as the Valar made war upon Melkor for the sake of the Quendi, so now for that time they forbore for the sake of the Hildor, the Aftercomers, the younger Children of Ilúvatar.
And how could Melkor communicate with Men?
Melkor could touch the minds of others
As indicated by @Ber, Melkor, like all Vala, had a great ability to communicate mind-to-mind, and crucially, to know what others were thinking.
For he would come by stealth to a mind open and unwary, hoping to learn some part of its thought before it closed, and still more to implant in it his own thought, to deceive it and win it to his friendship.
Through this, he could learn the language of Men, Elves, or whatever, so long as they were not wary of him.
Melkor may have learned their language, or taught them his own
He also was known by the Valar to have a great facility with language, such was his desire to use it to subvert the resistance of others to direct application of his will.
"From the first he was greatly interested in 'language,' that talent which the Eruhini would have by nature; but we did not at once perceive the malice in this interest, for many of us shared it, and Aule above all. But in time we discovered that he had made a language for those who served him, and he has learned our tongue with ease. He has great skill in this matter. Beyond doubt he will master all tongues, even the fair speech of the Eldar. Therefore, if ever you should speak with him, beware!"
This suggests that whatever language those early humans may have possessed, Melkor could have acquired it, especially considering that at first they were not wary.
Indeed, it is possible that he taught some humans his own language, as indicated in the previous text, which would both facilitate communication and make it easier to shape them to his purposes.
Per the Silmarillion, which I don't have at hand, the Valar were afraid that Morgoth would find the Elves before they did, which he did, and is why they engaged in the War of the Valar and Morgoth and destroyed Utumno.
It follows that Morgoth was similarly looking for Men. While in captivity in Valinor, he sent whispers to Fëanor and the Noldor that in their absence, Men would inherit Middle-earth. He also found Men in a similar location to where the Elves were already found. If we are going by Athrabeth.
Based on the account of Osanwë-kenta, Morgoth and Men both have an inherent capability to read one anothers' thoughts, much more so in the case of Morgoth and he could easily use this ability to learn the language of early Men. It can also be supposed that Men learned language from the Avari, whom Morgoth could already understand, having picked up language of the early Elves similarly (and subsequently much more familiar with them in Valinor).