Of course, one detail that gets looked at is whether a route matches. If I am sending to 192.0.2.55/24 and a route is available for traffic to 10.55.0.0/16 then that route is ignored because it doesn't apply.
The next criteria that is typically looked at is to have more specific routes have priority over more general routes. By "specific" route, I mean smaller subnets. In other words, bigger numbers when using /CIDR notation, and larger subnet masks when using "subnet mask" notation. In other words, destination networks with fewer possible addresses.
So, a "default gateway", also known as the "gateway of last resort", typically specifies a destination for all traffic to the 0.0.0.0/0 network. Any route for a smaller network will be "more specific" than that, and will take priority. So, 192.0.2.0/24 will have more priority.
Third, routes typically have another field called a "metric", or sometimes a different name like "priority". If you have multiple networks that are the same size, this can have an impact.
These "metric' values may be something that is generated automatically (e.g., that way a higher-speed network is used for more of the traffic), but can be adjusted manually.
Where is the information about the gateway to be taken encoded inside the IP packets sent?
The IP packets don't include any information about routing, except to specify the destination IP address. Routing details are determined by the equipment that handles the routing along the way, and such details are not typically placed in an IP packet. (Therefore, equipment does not look for such detail, since it is not there. Since equipment doesn't look for such information, it would be pointless to try to include such information.)
RFC 791 page 11 shows an "ASCII ART"-style table of the information that is in an IP packet. After that table, that document shows details (e.g., the "Options" section is described on page 15).