During the construction of a packet, your computer must first resolve any hostname used (eg, google.com) using the Domain Name System. Your computer will then have the destination IP address and you know know where to send the packet to, but do not know the route.
In order to determine this information, Every router maintains routing tables and one or more protocols are then used in order to determine the path of the packet. Typically, for small offices and homes, the protocol used is RIPv2. For the most simple setups, there is only one route - the default route which will route traffic through the default gateway of your firewall/router. At this point, you then reach an ISP router/cable modem. These will typically forward you via similar methods to a large router which use the BGP protocol. This is a much more complicated routing method in which large tables of routes are maintained which direct large public subnets assigned by companies like ARIN to designated routers. In the BGP protocol, these routes are updated by peers and expire and are refreshed periodically. For routing in between small and large scales (eg, within a large office or campus or an ISP, alternate protocols such as EIGRP or OSPF may be used
When the packet leaves your router, the source address is changed to be your router's public IP address. Thus when the packet reaches it's destination, the receiving server simply responds back to your router's address. It is then up to your router to track and maintain stateful connections - that is which source IPaddress:port and destination IPaddress:port combinations were communicating with each other. The creation, lifespan and teardown of these connections are maintained by your router based on it's firewall rules, NAT policies and other firewall settings.
On a lower level, network devices maintain ARP tables of which IP addresses should be sent to which MAC address connected to the device which maintains the table. So for example, with a home router, it knows to send the packet to the MAC address of your workstation or laptop and for all other traffic, it knows to send the packet to your cable modem or ISP router. To look up an address that has never before been seen, an ARP probe is broadcast and used to populate the table. This only tells each device it's next hop and ARP has no visibility to the next device (typically). (Eg, your workstation, will not know the MAC address of your Cable Modem/ISP Router. Only your router/WAP would.
