How do I make pagination_links show as 01 02 03, instead of 1 2 3?

Try switching the pagination type to array. That way you can use each link in a loop and add what you need to them:

Using the example from the codex:

global $wp_query;

$big = 999999999; // need an unlikely integer

echo paginate_links( array(
    'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
    'format' => '?paged=%#%',
    'current' => max( 1, get_query_var('paged') ),
    'total' => $wp_query->max_num_pages,
        'type' => array
) );

foreach ( $paginate_links as $link ) {
        echo sprintf("%02s", $link);
    }

The php sprintf function will add a leading zero.