OK, I just came up with something evil. But, I like it because it saves doing that extra assignment every time
StringBuilder qs = new StringBuilder();
bool firstKey = true;
foreach (KeyValuePair kvp in param)
{
qs.AppendFormat("{0}{1}={2}", (firstKey & !(firstKey = false) ) ? String.Empty : "&", kvp.Key, kvp.Value);
}