which action to hook to in order to perform post-publish action

You could hook into publish_post like the plugin Inform about Content does.

But this hook is fired on updates to published posts too, this may result in many redundant tweets …

Try 'draft_to_publish' instead. It is called in wp_transition_post_status() and happens only one time. You get the $post object as argument.

Prototype, not tested:

add_action( 'draft_to_publish', 'wpse_55516_tweet_new_post' );

function wpse_55516_tweet_new_post( $post )
{
    if ( 'post' !== $post->post_type )
    {
        return;
    }

    // Tweet it like a boss …
}