Well, they start off knowing nothing. In the IPv4 world, when host 'A' wants to talk to host 'B' it sends a broadcast arp (which every host receives) saying "who has IP address a.b.c.d, tell me". The host with the that IP address responds, and the original host now has the MAC address of host 'B'.
Apart from that, a host can also lean the MAC address of another host if a packet is unicast to it.