<p>The default output from Drupal's Form API is:</p>

<pre><code>&lt;input id="edit-submit" class="form-submit" type="submit" value="Save" name="op"/&gt;
</code></pre>

<p>How do I theme that so I get:</p>

<pre><code>&lt;button id="edit-submit" class="form-submit" type="submit"&gt;
  &lt;span&gt;Save&lt;/span&gt;
&lt;/button&gt;
</code></pre>

<p>I need the inner span-tag so I can use the sliding doors CSS technique.</p>

<p>I guess I need to override theme_button($element) from form.inc but my attempts so far have been unsuccessful.</p>

The basic idea to themeing a form_foo if you're using a plain PHP theme (like Chameleon), is to write a function called theme_form_foo().
You can also theme one element (like this button) specifically, by declaring a theme function just for it. See
https://api.drupal.org/api/drupal/developer%21topics%21forms_api_reference.html/7
Note that, with D6, in both cases you'll need to declare the function in the theme registry, otherwise Drupal won't notice this override. This is not necessary in D5. If you're using phptemplate, you'll need it too, although PHPtemplate takes care of the registry outside the forms case:
http://drupal.org/node/132442#theme-registry
The documentation for this is available on a.d.o. :
http://api.drupal.org/api/file/developer/topics/forms_api.html