How to theme the maintenance mode page?
You can edit or create a "maintenance-page.tpl.php" file in your theme directory and edit that to theme your maintenance page. 

You can view the source on the Drupal API page