Each "discovery" tool, like nmap, has its own recipe in matters of discovery, and you can make some very trivial scans as some more advanced. Each tool is not equivalent in terms of capability. In order to keep my answer simple, I will not describe all the internal tricks that a complex and exhaustive tool like nmap can do. (But you can find a complete description of how nmap works just on discovery here).
In terms of host discovery on the same subnet, the simplest and most basic way to do it, is to send pings to each IP address in the subnet, and expect a reply.
To give an answer to your question, the most widely used packets sent to do this are:
- ICMP type 8 (echo request), expecting a type 0 (echo reply)
- TCP SYN on a specific port, expecting a TCP ACK
The problem is that you will not discover hosts which do not choose to reply, like the ones running their own firewall.
Sending a broadcast packet is not a reliable solution either, because some hosts do not reply to broadcast, often for the same reason (their own firewall).
A way to make this technique more efficient is to check immediately the ARP table of the scanning host, and to check if there is any MAC address associated with the IP we sent the packet on just before, because ARP traffic is not blocked by an IP firewall.
If you want to go further, ARP discover is not reliable either on some networks (like some wireless spots) where security restricts traffic only between the host and the gateway. So you will not be able to "talk" to other hosts directly connected to the network, excepting the gateway.
Just one last thing: you are talking about "the network you are connected to". If the network contains several subnets, you lose the ARP visibility as soon as you are trying to scan another subnet than the one you are in (the ARP scope is never wider than the subnet).