Hi Brenden,
Don't think you should always maintain all parameters. As this would be a pain for instance when you have some paging or search via query string parameters.
If you could determine a set of parameters that need to be maintained I'd create a webpart or usercontrol and place that on the master page. Probably make this set of parameters manageable.
Think Javascript would be the quickest way to update all your links, but could go wrong on non redirecting links. So think 'Output filter' would be a good place to start.
Greets,
David