What is the most efficient way to add rows and columns to a matrix?

I would (and do) use Join to add both columns and rows:

Join[{v}, m] // MatrixForm
Join[List /@ v, m, 2] // MatrixForm

On my system -- 8.0.4 Mac 10.6.8 -- Join is faster than ArrayFlatten, although there is not a great deal in it:

m = RandomVariate[NormalDistribution[], {1000, 1000}];
v = RandomVariate[NormalDistribution[], 1000];

Do[tmp1 = ArrayFlatten[{{Transpose[{v}], m}}], {100}]; // AbsoluteTiming
Do[tmp2 = Join[List /@ v, m, 2], {100}]; // AbsoluteTiming
Do[tmp3 = Join[Transpose[{v}], m, 2], {100}]; // AbsoluteTiming
Do[tmp4 = Join[Partition[v, 1], m, 2], {100}]; // AbsoluteTiming

{1.614537, Null}
{1.538143, Null}
{1.523499, Null}
{1.519206, Null}

tmp1 == tmp2 == tmp3 == tmp4
True

ArrayFlatten is much faster than combination of Join and Transpose:

m = RandomVariate[NormalDistribution[], {1000, 1000}];
v = RandomVariate[NormalDistribution[], 1000];

Check that ArrayFlatten gives the same output:

(* In[54]:=*) ArrayFlatten[{{Transpose[{v}], m}}] == 
 Transpose[Join[{v}, Transpose[m]]]

(* Out[54]= True *)

(* In[57]:= *) ArrayFlatten[{{Transpose[{v}], m}}] == 
 MapThread[Prepend, {m, v}]

(* Out[57]= True *)

See the timing:

(* In[55]:= *) Do[
  ArrayFlatten[{{Transpose[{v}], m}}], {10^3}] // AbsoluteTiming

(* Out[55]= {4.330433, Null} *)

(* In[58]:= *) Do[MapThread[Prepend, {m, v}], {10^3}] // AbsoluteTiming

(* Out[58]= {11.766177, Null} *)

(* In[56]:= *) Do[
  Transpose[Join[{v}, Transpose[m]]], {10^3}] // AbsoluteTiming

(* Out[56]= {16.700670, Null} *)

For mcol you could use MapThread, which I would think would be better than transposing twice. So the following gives you what you want.

mcol = MapThread[Prepend, {m, v}]