How to do this is on the front of the plugins wordpress.org page.
http://wordpress.org/extend/plugins/wp-maintenance-mode/
You can add your own html and stylesheet and add the url of this style
to the options of the plugin. Write your style to this markup and
upload to the webspace; after add the url include http:// to the
settings of this plugin and change th theme to “Own Theme”:
Which while it is ambiguous, the settings page does offer an alternative. If you upload a dedicated maintenance html page, then use the redirect feature to redirect to it, you would have full control over the page.
It may be that this plugins themes are purely CSS based. You may be able to use the hooks and filters provided to remove and add items of content and markup, but redirects are the simplest method.
edit: After some talk with the plugin author, I’ve gotten the readme for the plugin and terminology changed, it seems if you put a wp-maintenance.php in wp-content it will use that instead of the default html.