For communication with machines in the same LAN, hosts do ARP for translating the IP address to MAC address, which means, IP addresses are already known to each other. My question is, how does the host come to know about the IP addresses of each other in the first place?
Some application on one hosts needs to communicate with an application on another host. Either the IP address of that other host is configured in the application, or DNS is used to look up the IP address of a name (for example www.example.com is converted 192.0.2.123).
if host A needs to communicate with host B, host A needs to know host's B address. It may be not an MAC or IP address, but it needs to be some address.
One common pattern is DNS, as described in other examples. Host B has a name. A network is running a service that allows to map host B's name to its current address. Important here is that (1) A has to know B's name, which btw can also be considered an address and (2) A knows how to reach DNS service, so A somehow knows its address.
There is a different available model, which is based on the concept of services. Services are some functions that can be performed by hosts/other network components. Some hosts provide services (aka are service providers). If other hosts want to use a service, they do service lookups which returns IP addresses of hosts(s) which provide the service. It can work other way around, each service provider periodically announses that it provides a service.
Service announcements and service lookups usually work by having well-known broadcast/multicast addresses for services. Service providers periodically broadcast announcement messages. Host, who lookup services, send discovery messages to well-known multicast addresses (and hope for reply :)). Examples of such a services are DHCP and IPv6 stateless address autoconfiguration.
Here is a wikipedia article for this. It has a couple of links with info. There is a mechanism called DNS-SD that allows to use DNS records for this. I think Multicast-DNS works like this too. And it has a couple of useful links.