Checking if a number is a Fibonacci or not?
Binet's formula tells you that $F_n$ is asymptotic to $\frac{1}{\sqrt{5}} \phi^n$, where $\phi = \frac{1 + \sqrt{5}}{2}$ is the golden ratio. So to check if a number $x$ is a Fibonacci number you should compute $n = \frac{\log (\sqrt{5} x)}{\log \phi}$. If this number is very close to an integer then $x$ should be very close to the Fibonacci number $F_{[n]}$ where $[n]$ denotes the closest integer to $n$. In fact I think $x$ is a Fibonacci number if and only if the error is less than about $\frac{\log \phi}{5x^2}$.
But if you don't trust that computation, you can compute $F_{[n]}$ in $O(\log n)$ time, for example by using binary exponentiation to compute powers of the matrix $\left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]$, and then you can check whether this number equals $x$.
Your first question can be answered using the theory of (generalized) Pell equations.
HINT $\rm\ n\:$ is a Fibonacci number iff the interval $\rm\ [\phi\ n - 1/n,\ \phi\ n + 1/n]\ $ contains a positive integer (the next Fibonacci number for $\rm\ n > 1\:$). This follows from basic properties of continued fractions. For one proof see e.g. $\ $ T. Komatsu: The interval associated with a fibonacci number. $\ $ This is a reasonably efficient test since it requires only a few multiplications and additions. $\ $ For example, $\rm\ 2 \to [2.7,\ 3.7],\ \ 3\to [4.5,\ 5.2],\ \ 5 \to [7.9,\ 8.3]\ \ldots$
As for ways to check is a number is a Fibonacci number, I'll speak to efficient testing since the other aspects seem covered. First, you should check if the residue mod some fixed number is possible for a Fibonacci number. Sloane's A189761 gives the sequence of 'good' moduli to use: for example, there are only 54 distinct residues mod 39088169 that contain Fibonacci numbers. A binary search on these lets you quickly remove 99.9998% of possible numbers. (Depending on how large you want to go, a smaller or larger number may be advisable.)
Of course for very small numbers you may choose to do a binary search directly before checking residues to the chosen modulus.
For numbers that pass the test, the 5n2 ± 4 test is best, and it's probably sensible to do this directly—the residue test above ensures that the number is not of a prohibited congruence class to your modulus. That is, compute the square root of the number and see if it is close to an integer. If so, square it and test if the result is the original number. The methods of Bernstein's paper "Detecting perfect powers in essentially linear time" (section 8) can be used here if desired.
Note that if n < 0 you need only test 5n2 + 4.