How to rewrite URI of custom post type?

The site that I am working on uses the following “pretty” permalink structure:

http://example.com/blog/my-special-post

But for a custom post type my client would like to avoid having a “pretty” slug:

http://example.com/product/142

How can the post ID be used in place of the slug for the custom post type?

I believe that this might be possible using WP_Rewrite, but I do not know where to begin.

This is what I use to rewrite custom post type URLs with the post ID. You need a rewrite rule to translate URL requests, as well as a filter on post_type_link to return the correct URLs for any calls to get_post_permalink():

add_filter('post_type_link', 'wpse33551_post_type_link', 1, 3);

function wpse33551_post_type_link( $link, $post = 0 ){
    if ( $post->post_type == 'product' ){
        return home_url( 'product/' . $post->ID );
    } else {
        return $link;
    }
}

add_action( 'init', 'wpse33551_rewrites_init' );

function wpse33551_rewrites_init(){
    add_rewrite_rule(
        'product/([0-9]+)?$',
        'index.php?post_type=product&p=$matches[1]',
        'top' );
}