In canon, we don't know. However, there are several possibilities which seem reasonable.
1. Socialising among house-elves.
House-elves can Apparate, unfettered by the restrictions on wizard Apparition, so meetings between house-elves working for different wizarding families would be easy to arrange, even without their masters knowing about it. But given the servile nature of most house-elves, it seems unlikely that they'd do this without their masters' permission, or indeed at all unless it was on their masters' business. However, visiting each other on their master's business would be entirely reasonable. If the Crouches were visiting the Malfoys for dinner, for instance, Winky might nip over to tell Dobby about their eating habits and so on beforehand.
2. Socialising among wizards, with house-elves tagging along.
We saw at the end of HP and the Chamber of Secrets that Lucius Malfoy takes his house-elf with him when he goes to Hogwarts on business. If he, or for that matter Crouch, makes a habit of this, it would make a good opportunity for Winky and Dobby to have met and got to know each other. Whatever their opinions of each other may have been, the Malfoys and the Crouches probably had to interact a good deal in the course of their work at the Ministry. Lucius Malfoy and Barty Crouch Jr. may also have met through Death Eater circles at some point.
3. Dobby's adventures and unemployment.
After his escape from the Malfoys and subsequent unemployment, Dobby is likely to have become something of a legend (or more likely infamous) among house-elves. If any of them have any social contact with each other whatsoever, he's likely to have been a hot topic, especially after he began to have some more self-respect and look for paid work. It may even be that the Crouch family was one of the places he applied for work - with Winky tied up looking after Jr. most of the time, Sr. might well have wanted more elf labour in his house.
...
For more discussion of this issue, see this Reddit thread or this lengthy CoS Forums thread.
