Add query parameter from url to all links on the page
You can do it easily in a custom module, implementing hook_url_outbound_alter().

function mymodule_url_outbound_alter(&amp;$path, &amp;$options, $original_path) {
  $param = $_GET['q'];
  $path = 'build-path-as-desired.';
}


That should do it for you. The hook serves, basically, to alter outbound urls. You can look at the documentation for it in the system.api.php file, and I suggest you do that, as there are a couple of things to take into account when altering urls through it, but it's definitely an easy way of doing what you want to do.

EDIT: Online documentation for the hook - https://api.drupal.org/api/drupal/modules%21system%21system.api.php/function/hook_url_outbound_alter/7

EDIT 2: Additional functions to work with the path being requested:
drupal_get_query_parameters() and drupal_get_path_alias($path).