[gallery]

It’s worse than that as well… because the CSS is added to the content, it is added for every post that uses it.
This means that if you have different layout/css for different gallery pages (e.g. 3/4 column layout [gallery columns="3"] etc.) Then when viewing an archive, or an overall blog view when more than one post is on a page at a time, then the last shown post will override the gallery style… Not good.

Or better still, rather than hack the core code…
write a plugin to do it…

Something like this should do the trick, copy all the code and paste into a file called gallerycss.php, make sure you have no white space before or after the php tahs (<? and ?>), upload to your plugins folder and activate. (At your own risk)

<?php
/*
Plugin Name: Move Gallery CSS from body to head
Plugin URI: http://wordpress.org/support/topic/164825?replies=5#post-722329
Description: Removes the Gallery CSS declaration and adds into the head
Author: Dickie
Version: 1.0
Author URI:
*/

function test_gallery_removecss($css)
{
	// Note you still need to return the start div
	return '<div class=\'gallery\'>';
}

function test_gallery_addcss()
{
	// Note this is limited to 3 wide column width only
	echo '<style type=\'text/css\'>
			.gallery {
				margin: auto;
			}
			.gallery-item {
				float: left;
				margin-top: 10px;
				text-align: center;
				width: 33%;
			}
			.gallery img {
				border: 2px solid #cfcfcf;
			}
			.gallery-caption {
				margin-left: 0;
			}
		</style>';
}
add_filter('gallery_style', 'test_gallery_removecss');
add_action('wp_head','test_gallery_addcss');
?>

Note though that using this you would no longer be able to use the column reference in the gallery shortcode, as that is calculated into the CSS code we have just overridden.
(e.g. [gallery columns="4"] ), to do that you need to change the %age width in the css in the plugin.