I know that media are an attachment post type that are children to a post, but how are galleries stored in WordPress?
This completely depends on how your gallery shortcode looks like.
If you replaced it with something custom, then you'll have to take a look at the plugin (or the theme).
The default gallery shortcode gets it from a query:
$query_args = array( 'post_status' => 'inherit' ,'post_type' => 'attachment' ,'post_mime_type' => 'image' ,'order' => $order ,'orderby' => $orderby );
Then it decides to add additional args for either
Here're the 3 scenarios that add the additional/non-shared arguments.
'include' => preg_replace( '/[^\D,]+/', '', $include ) 'exclude' => preg_replace( '/[^\D,]+/', '', $include ) // default 'post_parent' => $id