As described by István this is an issue of evaluation order.  There are several methods, `Evaluate` and `With` already illustrated.  I often use a `Function` for this purpose as it is concise:

    paramToVary = a;
    paramValues = Range[0, 1, 1/5];
    
    Table[{a, b}, {#, paramValues}] & @ paramToVary

>     {{0, b}, {1/5, b}, {2/5, b}, {3/5, b}, {4/5, b}, {1, b}}

There are potential complications with your approach that I wish to caution you about.  If the Symbol `a` has an assigned value this operation will fail because `paramToVary` will evaluate to that value rather than the Symbol `a`:

    a = 999;
    Table[{a, b}, {#, paramValues}] & @ paramToVary

> During evaluation of In[42]:= Table::itraw: Raw object 999 cannot be used as an iterator. >>

You can guard against this by keeping the Symbol in a `Hold` expression, and by using some method to insert the unevaluated Symbol into the `Table` (or `Do`) expression.  My favorite method for the latter is what I have come to call the ["injector pattern"][1].  Please also see http://mathematica.stackexchange.com/q/19758/121 for a related question.

    a = 999;

    paramToVary = Hold[a]
    
    paramToVary /. _[x_] :> Table[{a, b}, {x, paramValues}]

>     {{0, b}, {1/5, b}, {2/5, b}, {3/5, b}, {4/5, b}, {1, b}}

Note that `a` had a value before `paramToVary` was defined without breaking the code.

Alternatively you can use [my `step` function][2] which simplifies definition retrieval, and use `SetDelayed` rather than `Hold`:

    a = 999;
    
    paramToVary := a;
    
    step[paramToVary] /. _[x_] :> Table[{a, b}, {x, paramValues}]

>     {{0, b}, {1/5, b}, {2/5, b}, {3/5, b}, {4/5, b}, {1, b}}


  [1]: http://mathematica.stackexchange.com/a/1937/121
  [2]: http://mathematica.stackexchange.com/questions/334/how-do-i-evaluate-only-one-step-of-an-expression/1447#1447