Adding parameters to $header links
The code that outputs the links for the table header is contained in tablesort_header().

$cell['data'] = l($cell['data'] . $image, $_GET['q'], array('attributes' =&gt; array('title' =&gt; $title), 'query' =&gt; array_merge($ts['query'], array('sort' =&gt; $ts['sort'], 'order' =&gt; $cell['data'])), 'html' =&gt; TRUE));


The function is called from theme_table(), which is the theme function used to render a table.  

What you can do is implementing your theme function that is then used to render the table your module is outputting. There isn't any other method, as theme_table() is not getting any parameter that changes the URL for the table header; as such, implementing hook_preprocess_table() would not achieve anything.

To implement a theme function, you need to declare it using hook_theme().

function mymodule_theme($existing, $type, $theme, $path) {
  return array(
    'mymodule_table' =&gt; array(
      'variables' =&gt; array('header' =&gt; NULL, 'rows' =&gt; NULL, 'attributes' =&gt; array(), 'caption' =&gt; NULL, 'colgroups' =&gt; array(), 'sticky' =&gt; TRUE, 'empty' =&gt; ''),
    ),
  ); 
}


Once you declared the theme function, you can use it as you used theme_table(), simply replacing any call to theme('table', /* the rest of the arguments */) with theme('mymodule_table', /* the rest of the arguments */). Notice that in hook_theme() the theme function is referred as mymodule_table, but the PHP function is theme_mymodule_table().

The code you need for your theme function is the same used by theme_table(), except that instead of calling tablesort_header() it will call your own function.

foreach ($header as $cell) {
  $cell = tablesort_header($cell, $header, $ts); // Replace it with the call to your function.
  $output .= _theme_table_cell($cell, TRUE);
}