What is the correct way for a theme to support plugin UIs?

First of all, provide a well-formed default HTML form. Use <label>, <fieldset> and <legend> where appropriate. This markup provides a good structure for CSS styling. Adding in some CSS classes may help too.

Provide a filter that allows developers to tweak the default form.

To go even further, you can allow developers to completely rewrite the form output to their likings by allowing them to provide a custom form template file within a theme.

if ($custom_form = locate_template('plugin_form.php')) {
    // Load custom form
    include $custom_form;
} else {
    // Default form with filter
    $form = '<form><!-- Default HTML --></form>';
    $form = apply_filters('pluginprefix_form_output', $form);
    echo $form;
}

Have a look at the get_search_form() function in wp-includes/general-template.php for a good example of a similar implementation.