The main problem here isn't so much NextGen Gallery as the Google image bot. It's a slow bot and doesn't index images quite as much as a lot of site owners would like.
That said, NGGallery could be improved slightly. The alt tag uses the image's title where it should really use the description. I've reworked my sites to the title is the title and the description is the alt tag.
$this->href .= '<img alt="'.$this->alttext.'" src="'.$this->imageURL.'"/>'."\n".'</a>'."\n";
$this->href .= '<img title="'.$this->alttext.'" src="'.$this->imageURL.'" alt="'.htmlspecialchars( stripslashes($this->description) ).'" />'."\n".'</a>'."\n";
The alt tag and image filename are the key elements for the Google image bot, so many could optimise their images and use the title and descriptions in NGGallery better.
Then, unfortunately, it's a question of waiting and a little hoping.
And doing all the usual website promotion.