How to theme the maintenance mode page? What would be the best practice for theming the maintenance mode page in Drupal 7?
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