I found a solution after a lot of digging.
First, you have to find the views-exposed-form.tpl.php file which should be located in sites/all/modules/views/theme/ folder. We're using the acquia stack so it was located in the vendor/ folder.
Copy this to themes/YOUR-THEME/ folder and rename it to views-exposed-form--your-view-name.tpl.php
If you only want to effect a specific display of your view name it to views-exposed-form--your-view-name--display.tpl.php
You can then use the existing framework to edit it as you see fit. Here's an example.
<?php
// $Id: views-exposed-form.tpl.php,v 1.4.4.1 2009/11/18 20:37:58 merlinofchaos Exp $
/**
* @file views-exposed-form.tpl.php
*
* This template handles the layout of the views exposed filter form.
*
* Variables available:
* - $widgets: An array of exposed form widgets. Each widget contains:
* - $widget->label: The visible label to print. May be optional.
* - $widget->operator: The operator for the widget. May be optional.
* - $widget->widget: The widget itself.
* - $button: The submit button for the form.
*
* @ingroup views_templates
*/
?>
<?php if (!empty($q)): ?>
<?php
// This ensures that, if clean URLs are off, the 'q' is added first so that
// it shows up first in the URL.
print $q;
?>
<?php endif; ?>
<div class="views-exposed-form">
<div class="views-exposed-widgets clear-block">
<?php foreach($widgets as $id => $widget): ?>
<div class="views-exposed-widget">
<?php if (!empty($widget->label)): ?>
<label for="<?php print $widget->id; ?>">
<?php print $widget->label; ?>
</label>
<?php endif; ?>
<?php if (!empty($widget->operator)): ?>
<div class="views-operator">
<?php print $widget->operator; ?>
</div>
<?php endif; ?>
<div class="views-widget">
<?php print $widget->widget; ?>
</div>
</div>
<?php endforeach; ?>
<div class="views-exposed-widget">
<?php print $button ?>
</div>
</div>
</div>