The results from considering $10^6$ pseudorandom $X_n$ for $n\leq 200$ suggest that the probability of being zero might decay exponentially:

[![probability of $X_n$ being zero versus $n$][1]][1]

The best exponential fit is something like $e^{-1.18-0.0764n}$. The base of the exponential growth is $e^{-.0764}\approx0.926$ which is consistent with the upper bound from Gjergji Zaimi's answer of $(27/32)^{1/3}\approx0.945$.

The probability density function for the number of zeroes in each sequence also seems to decay exponentially (the y-axis ought to read "Probability of having $z$ zeroes in $\{X_i\}_{i=0}^{200}$", and this plot really should start at $z=1$, rather than $z=0$):

[!["Probability of having $z$ zeroes in $\{X_i\}_{i=0}^{200}$" versus $z$][2]][2]

The best exponential fit is something like $0.618e^{-0.481z}$. 

These were produced with the following Mathematica code (with apologies to [Mathworld's page](http://mathworld.wolfram.com/RandomFibonacciSequence.html)):

    max = 200;
    max2 = 10^6;
    stats = Table[m = #[[1, 1]] & /@ FoldList[Dot, IdentityMatrix[2], {{0, 1}, {1, #}} & /@ ((-1)^Table[Random[Integer], {max}])];
    Flatten[Position[m, 0], 1], {max2}]; 
    numstats = Tally[Table[Length[stats[[i]]], {i, max2}]];
    numstats2 = Table[{numstats[[i, 1]], numstats[[i, 2]]/max2}, {i, Length[numstats]}];
    ListLogPlot[numstats2, AxesLabel -> {"z", "probability of z zeros in \!\(\*SubscriptBox[\(X\), \(0\)]\) to \\!\(\*SubscriptBox[\(X\), \(200\)]\)"}]
    fstats = Tally[Flatten[stats, 1]];
    fstats2 = Table[{fstats[[i, 1]] - 2, fstats[[i, 2]]/max2}, {i, Length[fstats]}];
    ListLogPlot[fstats2, AxesLabel -> {"n", "probability of \!\(\*SubscriptBox[\(X\), \(n\)]\) being zero"}]


  [1]: https://i.sstatic.net/5azmw.png
  [2]: https://i.sstatic.net/tz4e8.png