url rewriting for custom post types

Yes you can use the rewrite parameter when creating your custom post type:

register_post_type( 'example_type',
      array(
          'labels' => array(
              'name' => "Example-Type",
              'singular_name' => "example-type"
          ),
          'public' => true,
          'has_archive' => true,
          'rewrite' => array('slug' => 'the-url-you-want',
      )
  );
}

You will need to reset your permalinks for it to take effect as well.

EDIT:

function custom_post_link( $post_link, $id = 0 ){
    $post = get_post($id);  
    if ( is_object( $post ) ){
        $terms = wp_get_object_terms( $post->ID, 'category' );
        if( $terms ){
            return str_replace( '%category%' , $terms[0]->slug , $post_link );
        }
    }
    return $post_link;  
}
add_filter( 'post_type_link', 'custom_post_link', 1, 3 );