Original
Use this code DiscretePlot[fib[n], {n, 0, 20}] or ListPlot[Table[fib[n], {n, 0, 20}]] rather than Plot. Plot is intended for continuous-valued functions, not functions that are explicitly intended only to be defined over non-negative integers, as is the case here.
Clear[fib];
fib[0] := 1;
fib[1] := 1;
fib[n_] := fib[n - 1] + fib[n - 2];
DiscretePlot[fib[n], {n, 0, 10}]

ListPlot[Table[fib[n], {n, 0, 10}]]

Edit
If you use recurrence relation with RSolve like this, you would get the general formula that is applied to Plot as continuous function.
fb = f[n] /.
RSolve[{f[n] == f[n - 1] + f[n - 2], f[1] == f[0] == 1}, f[n], n][[1]]
1/2 (Fibonacci[n] + LucasL[n])
Plot[fb, {n, 0, 10},
Prolog -> DiscretePlot[fib[n], {n, 0, 10}][[1]]]

DiscretePlot[fib[n], {n, 0, 20}]orListPlot[Table[fib[n], {n, 0, 20}]]rather thanPlot$\endgroup$Plot[]when you need to use continuous functions, like inPlot[Sin[x], {x, 0, 2 Pi}]$\endgroup$