All curves in plot have the same style. Cannot be fixed with Evaluate[]

Evaluate is necessary in this simple case because

Plot has attribute HoldAll, and evaluates f only after assigning specific numerical values to x

and because Plot determines automatic styles based on the unevaluated form of f. When you call Plot[Table[ ... ], ...], Plot looks at its first argument, Table[ ... ], without evaluating it and notes that it has a length of 1, and it constructs style specifications based on that information. You can override this behavior of Plot by applying Evaluate to its first argument.

A simple way to accomplish what you want is to redefine g so that it wraps its output with Hold:

g[y_] := Hold@Total[Table[1, {z, 1, Round[y + 1]}]]
Plot[Evaluate@Table[g[n*x], {n, 1, 3}], {x, 0, 1}]

This works because the evaluated form of the first argument to Plot is now

{Hold[Total[Table[1, {z, 1, Round[x + 1]}]]], Hold[Total[Table[1, {z, 1, Round[2 x + 1]}]]], Hold[Total[Table[1, {z, 1, Round[3 x + 1]}]]]}

which does have a length of 3, and it doesn't produce an error because each of these three forms is held unevaluated until they are inside an environment that has a value bound to x.

Note that this variation

g[y_] := Total[Table[1, {z, 1, Round[y + 1]}]]
Plot[Evaluate@Table[Hold@g[n*x], {n, 1, 3}], {x, 0, 1}]

does not work, because it prevents g from being evaluated at all - we want g to be expanded with different values of n.

Evaluate@Table[Hold@g[n*x], {n, 1, 3}]
(* == {Hold[g[n x]], Hold[g[n x]], Hold[g[n x]]} *)

You could use the splitstyle function from this question :

splitstyle[styles__]:=Module[{st=Directive/@{styles}},{{Last[st=RotateLeft@st],#}}&];

g[y_]:=Total[Table[1,{z,1,Round[y+1]}]];

Plot[Table[g[x*n],{n,1,3}],{x,0,1},PlotStyle->splitstyle[Red,Green,Blue]]

Or to use the standard colours:

Plot[Table[g[x*n],{n,1,3}],{x,0,1},PlotStyle->splitstyle@@ColorData[1]/@{1,2,3}]

(Note: This does not work in Mathematica 11.)

Sadly the undocumented mechanism behind Simon's splitstyle no longer works in Mathematica 10.0 or 10.1. Post-processing^(1),(2) remains an option as does use of ListPlot. While pure post-processing is possible, in a bid to make this answer unique I shall instead define styleSplitter as a function that extracts the PlotStyle option from an unevaluated Plot expression. If none is present the default for that plot type is taken from Options.

(This function can be viewed as a derivative of xslittlegrass's restylePlot2 that pulls style information from the Plot expression itself.)

SetAttributes[styleSplitter, HoldFirst]

styleSplitter[plot : h_[___, op : OptionsPattern[]]] :=
 MapAt[
   ListLinePlot[Cases[Normal @ #, Line[x__] :> x, -3]
   , PlotRange -> Full
   , PlotStyle -> OptionValue[h, {op}, PlotStyle] ][[1]] &
   , plot
   , 1
 ]

Test:

g[y_] := Total[Table[1, {z, 1, Round[y + 1]}]];

Plot[
  Table[g[x*n], {n, 1, 3}], {x, 0, 1},
  PlotStyle -> {Blue, Orange}
] // styleSplitter

Because styling is done by ListLinePlot itself automatic behaviors such as style cycling are preserved.