Every host has a routing table. It contains subnets, with network numbers and netmasks, and interfaces. For instance (simplified):
0.0.0.0/0 eth0 via 172.16.1.1
172.16.1.0/24 eth0 local
10.0.0.0/8 eth1 local
127.0.0.0/8 lo local
The most specific one is used. So, for instance, the host 172.16.1.2 is on the 172.16.1.0/24 subnet, so the routing table tells us to just send it out eth0.
If it was 10.0.1.2, it would be on 10.0.0.0/8, so we would send it locally on eth1 (and not via a gateway, either).
If we were connecting to 22.214.171.124, the routing table has no route more specific than the default route (0.0.0.0/0), so it sends it out via the default gateway (172.16.1.1), which in turn will pass it on using its routing table (this is called a hop). Eventually, a router will be found that has a local route for 126.96.36.199, and then the packet will reach its destination.
That is a simplification, but it's basically how it works.
The network doesn't itself know or really do anything; hosts and routers do all the work ;)
On a router, the routing table is usually generated by using a routing protocol (such as BGP, or cisco's EIGRP) to discover adjacent routers, and the most efficient path is found by adding a metric (cost) to each route, so that the most specific route with the lowest cost is selected to pass the packet through.
If the packet ends up in a loop, or hits a dead end (gets routed to a router that has nowhere to send it), the packet will be dropped, and an ICMP failure message will sometimes be returned to you.