Can a shortcode included in post content add styles to the ?

hook the_posts and inspect each post to see if your shortcode is present, you can use wp_enqueue_style at that point if it is. maybe a bit of regex to check for the presence of the shortcode is the way to go, unfortunately i’m not very good with regex!

function wpse27772_has_shortcode($posts) {
    if ( empty($posts) )
        return $posts;

    $has_shortcode = false;

    foreach ($posts as $post) {
        //check for your shortcode in $post->post_content
        //set $has_shortcode = true if it's found
    }

    if($has_shortcode === true):
        wp_enqueue_style( 'mystyle', get_template_directory_uri().'/mystyle.css' );
    endif;

    return $posts;
}
add_action('the_posts', 'wpse27772_has_shortcode');

EDIT – quick example from my comment below…

function wpse27772_output_styles(){
    global $posts;
    foreach ($posts as $post) {
        // inspect $post->post_content;
        // echo "<style type="text/css"></style>";  
    }
}
add_action('wp_head', 'wpse27772_output_styles');