I had a similar scenario once and I found this article by Peter Bromberg very helpful :

I have a 'class' that does this and here it is:

function QS(){
    this.qs = {};
    var s = location.search.replace( /^\?|#.*$/g, '' );
    if( s ) {
        var qsParts = s.split('&');
        var i, nv;
        for (i = 0; i < qsParts.length; i++) {
            nv = qsParts[i].split('=');
            this.qs[nv[0]] = nv[1];
        }
    }
}

QS.prototype.add = function( name, value ) {
    if( arguments.length == 1 && arguments[0].constructor == Object ) {
        this.addMany( arguments[0] );
        return;
    }
    this.qs[name] = value;
}

QS.prototype.addMany = function( newValues ) {
    for( nv in newValues ) {
        this.qs[nv] = newValues[nv];
    }
}

QS.prototype.remove = function( name ) {
    if( arguments.length == 1 && arguments[0].constructor == Array ) {
        this.removeMany( arguments[0] );
        return;
    }
    delete this.qs[name];
}

QS.prototype.removeMany = function( deleteNames ) {
    var i;
    for( i = 0; i < deleteNames.length; i++ ) {
        delete this.qs[deleteNames[i]];
    }
}

QS.prototype.getQueryString = function() {
    var nv, q = [];
    for( nv in this.qs ) {
        q[q.length] = nv+'='+this.qs[nv];
    }
    return q.join( '&' );
}

QS.prototype.toString = QS.prototype.getQueryString;

//examples
//instantiation
var qs = new QS;
alert( qs );

//add a sinle name/value
qs.add( 'new', 'true' );
alert( qs );

//add multiple key/values
qs.add( { x: 'X', y: 'Y' } );
alert( qs );

//remove single key
qs.remove( 'new' )
alert( qs );

//remove multiple keys
qs.remove( ['x', 'bogus'] )
alert( qs );

I have overridden the toString method so there is no need to call QS::getQueryString, you can use QS::toString or, as I have done in the examples just rely on the object being coerced into a string.

Ok here I compare Two functions, one made by myself (regExp) and another one made by (annakata).

Split array:

function insertParam(key, value)
{
    key = escape(key); value = escape(value);

    var kvp = document.location.search.substr(1).split('&');

    var i=kvp.length; var x; while(i--) 
    {
        x = kvp[i].split('=');

        if (x[0]==key)
        {
                x[1] = value;
                kvp[i] = x.join('=');
                break;
        }
    }

    if(i<0) {kvp[kvp.length] = [key,value].join('=');}

    //this will reload the page, it's likely better to store this until finished
    return "&"+kvp.join('&'); 
}

Regexp method:

function addParameter(param, value)
{
    var regexp = new RegExp("(\\?|\\&)" + param + "\\=([^\\&]*)(\\&|$)");
    if (regexp.test(document.location.search)) 
        return (document.location.search.toString().replace(regexp, function(a, b, c, d)
        {
                return (b + param + "=" + value + d);
        }));
    else 
        return document.location.search+ param + "=" + value;
}

Testing case:

time1=(new Date).getTime();
for (var i=0;i<10000;i++)
{
addParameter("test","test");
}
time2=(new Date).getTime();
for (var i=0;i<10000;i++)
{
insertParam("test","test");
}

time3=(new Date).getTime();

console.log((time2-time1)+" "+(time3-time2));

It seems that even with simplest solution (when regexp use only test and do not enter .replace function) it is still slower than spliting... Well. Regexp is kinda slow but... uhh...

Have you searched for javascript url parsers ? You could make your own, splitting on every &-character, but it's probably easier just to use existing code.

I'll have a go. I'd do something like this:

function constructQuery(newkey, newvalue) {
	// the url will be split into three pieces
	var stem = window.location.href; 
	var query = "";
	var anchor = "";

	// split off the anchor
	var anchorindex = stem.lastIndexOf("#");
	if(anchorindex != -1) {
		anchor = stem.substring(anchorindex);
		stem = stem.substring(0, anchorindex);
	}

	// split off the query
	var queryindex = stem.lastIndexOf("?");
	if(queryindex != -1) {
		query = stem.substring(queryindex+1);
		stem = stem.substring(0, queryindex+1);
	}
	else{ stem += "?"; }

	// rewrite the query
	if(query != "") {
		var parameters = query.split("&");
		var newquery = "";
		for(int i = 0; i < parameters.length; ++i) {
			var parameter = parameters[i].split("=");
			if(parameter[0] == newkey) { continue; }
			if(newquery.length > 0) { newquery += "&"; }
			newquery += parameter;
		}
		query = newquery + "&" + newkey + "=" + newvalue;
	}

	// recombine the three pieces
	return stem + query + anchor;
}

I made up this code just then so I hope I've thought through everything but I might've missed something. I don't know if it even compiles, but at least you get the idea.