How many digits of accuracy will an answer have?

You do not really need to work in floating point: Fibonacci numbers fulfill interesting duplication identities, so there are fast algorithms in integer arithmetic, as Brevan Ellefsen mentioned.

Here it is some $\text{Maxima}$ code for the fast computation of the $n$-th Fibonacci number.

 /* Fast Fibonacci Numbers Computation */
 fastfib(n):=block([O:2,L:?integer\-length(n),i,f0:2,f1:1,u,v],
   for i:1 thru L do (
    u:f0^2, v:f1^2,
    if ?logbitp(L-i,n) then (f1:v+O, f0:f1-u+O, O:-2  )
                       else (f0:u-O, f1:v+O-f0, O:2   )),
  return((?ash(f1,1)-f0)/5)
  );

This is included in the $\text{gf}$ package. In order to compute $F_n$, we just need to compute $2\log_2(n)$ squares. With Karatsuba algorithm (invoked in $\text{Maxima}$ through the $\text{fasttimes}$ command) or similar approaches the computation of $m^2$ requires just $\log_2(m)^{1.585}$ elementary operations.

This is pretty efficient. Here it is some test on my machine:

Maxima 5.32.1 http://maxima.sourceforge.net
using Lisp GNU Common Lisp (GCL) GCL 2.6.10 (a.k.a. GCL)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) load("gfpatch.mac");
(%o1)                             gfpatch.mac
(%i2) showtime:true;
Evaluation took 0.0000 seconds (0.0000 elapsed)
(%o2)                                true
(%i3) fastfib(10000000)$
Evaluation took 0.0800 seconds (0.0900 elapsed)

Back to the actual question: since $\phi^n=\exp(n\log\phi)$ and $\frac{d}{dx}x^n = n x^{n-1}$, we roughly have $(\phi+\varepsilon)^n \approx \phi^n+n\varepsilon\phi^{n-1}$, so a good accuracy is achieved as soon as $\varepsilon\ll\frac{1}{n\phi^{n-1}}$, and we need to store $\approx 0.7n$ binary digits of $\varphi$ to compute $\varphi^n$ with decent accuracy.

You could definitely improve the calculations by considering only $\phi$ $$F_n=\left[\frac{\phi^n}{\sqrt{5}}\right]$$ Re the error, taking a $\phi^{*} \in \mathbb{Q}$ such that $|\phi - \phi^{*}|<\frac{1}{n2^{n-1}10^m}$, leads to: $$|\phi^n - (\phi^{*})^n|=|\phi - \phi^{*}|\cdot |\phi^{n-1}+\phi^{n-2}\phi^{*}+...+(\phi^{*})^{n-1}|\leq |\phi - \phi^{*}|\cdot n2^{n-1}<\frac{1}{10^m}$$

On another note, the very same wikipedia article suggests a procedure that: