Create a template for the page

Let's say I have this implementation of hook_menu():

function example_menu(){
    $items = array();

    $items['admin/recent-completions'] = array(
        'title' => 'Recent Completions (Last 100)',
        'page callback' => 'example_recent',
        'access callback' => user_access('Administer content'),
        'type' => MENU_NORMAL_ITEM,
        'weight' => -50
    );

    return $items;
}

How can I make a template for the page callback instead of returning a string?

You would need to implement a hook_theme function and specify a template file.

Then in your page callback, you would have to call your theme function. Something like...

function example_theme($existing, $type, $theme, $path) {
  return array(
    'recent_completion' => array(
      'render element' => 'elements', 
      'template' => 'recent-completions',
    ), 
  ...
}

function example_recent() {
  // Do some logic and processing here
  $render_array = array( /* array with parameters for the template */ );
  return theme('recent_completion', $render_array);
}