With an extra endpoint
Since you want to add something to the end of every post/page rewrite rule, you probably can just add a rewrite endpoint. These are regexes of the form /[endpoint_name](/[optional_extra_stuff])? that are appended to the already generated rules for pages, posts, archives, ...
You define on which structures you want to add them by setting the endpoint mask. This is a bitmask, so you can combine different groups using the | operator, like this: EP_PERMALINK | EP_PAGES will match for every page and every permalink (full post and date-based archives). The default list of endpoints can be found at the top of wp-includes/rewrite.php.
The following code will add /gallery(/(.*))? to the existing rewrite rules for pages, posts and date-based archives (for some reason they are generated twice, once in EP_PERMALINK and once in EP_DATE):
add_filter( 'init', 'wpse4498_init' );
function wpse4498_init()
{
add_rewrite_endpoint( 'gallery', EP_PERMALINK | EP_PAGES );
}
With explicit new rewrite rules
You can also do is explicitly, which might give you more control over the generated rules.
The rewrite rule itself it quite easy: take the generic post rule (.+?)/([^/]+) (category/pagename) and add your gallery structure. NextGEN always adds its query vars, not only when permalinks are enabled, so we can just use the gallery var:
'(.+?)/([^/]+)/gallery/([0-9]{1,})/?$' =>
'index.php?category_name=$matches[1]&name=$matches[2]&gallery=$matches[3]'
The placement of your extra rewrite rule is tricky. Since your permalink structure is /%category%/%postname%/ you have verbose rewrite rules, and can't put a generic (.+?)/([^/]+) at the top: your pages will stop working. You can't put it at the bottom, as the attachment rules are quite generic and will have matched the URL before it reaches your rule. I think the best place to add it is with the post_rewrite_rules filter. This will give the following:
add_filter( 'post_rewrite_rules', 'wpse4498_post_rewrite_rules' );
function wpse4498_post_rewrite_rules( $post_rewrite_rules )
{
$post_rewrite_rules = array(
'(.+?)/([^/]+)/gallery/([0-9]{1,})/?$' =>
'index.php?category_name=$matches[1]&name=$matches[2]&gallery=$matches[3]',
) + $post_rewrite_rules;
return $post_rewrite_rules;
}
This only covers posts, if you also want to support pages with galleries it will become much more complicated since you have to add them for each verbose page group.