A host that sends something to another host needs to resolve a layer-2 address from the layer-3 address in order to create a layer-2 frame to encapsulate the layer-3 packet. That is where ARP (Address Resolution Protocol) comes in.
A host should maintain a resolution table for ARP. This table is indexed by layer-3 address, and the information is the layer-2 address. This table will be empty when a host starts up, and table entries should eventually time out.
When a host needs to resolve a layer-2 address from a layer-3 address (each time it sends a layer-3 packet to layer-2 for encapsulation), the host will search the resolution table for the layer-3 address. If there is no entry for that layer-3 address in the resolution table, the host will broadcast an ARP request. If no reply is received in a certain amount of time, the packet will be dropped, and an ICMP message sent to the application telling it that the host is unreachable. When a reply is received from the destination host, its layer-3 and layer-2 addresses are added to the table, and the next time a host needs to send a layer-3 packet to the destination host, it will have the resolution in its table, at least until the table entry times out.
This process happens even when the destination host is on a different network, but in that case, the layer-2 destination host will be the host's configured gateway.
From the perspective of layer-2, a router is just another host on the LAN, and ARP functions the same way for a router as for any other host on the LAN.
The ARP process is detailed in RFC 826, An Ethernet Address Resolution Protocol -- or -- Converting Network Protocol Addresses to 48.bit Ethernet Address for Transmission on Ethernet Hardware.