A matrix of order 8 over $\mathbb{F}_3$

Using a similar strategy to Travis, we can actually answer this question quite nicely: $$A \text{ has order 8 if and only if }\det(A) = 2 \text{ and } \text{tr}(A) \neq 0.$$ We can do this by looking at the characteristic polynomial $p(x)$ of $A$, with which we can utilize the fact that $p(A) = 0$ as shown below.

Since $A$ is a $2\times 2$ matrix, this takes the simple form $p(x) = x^2 - tx + d$ where $t$ is the trace of $A$ and $d$ the determinant (which cannot be 0 since $A$ is invertible). If the trace is 0, then $A^2 = dI$ and so has order $2$ if $d = 1$ and 4 if $d = 2$. Thus if we are looking for an invertible matrix $A$ with order 8, we know that $d$ and $t$ must be nonzero.

We can now calculate powers of $A$ quite readily through successive squaring, use two key observations to simplify the calculations: 1)in $\mathbb{F}_3$, 2 is the same as $-1$ and so we can replace any appearance of 2 with a negative sign and 2) since $t$ and $d$ are both either $1$ or $2 = -1$, it is always true that $t^2 = d^2 = 1$. The calculations in $\mathbb{F}_3$ are as follows, using the fact that $p(A) = 0$: $$A^2 = tA-dI$$ $$ A^4 = (tA-dI)^2 = A^2+tdA + I = t(1+d)A + (1-d)I,$$ $$ A^8 = (1+d)^2A^2+(1-d)^2I = -(d+1)A^2 + (d-1)I$$ $$\implies A^8 = [d(d+1)+(d-1)]I - t(d+1)A = -dI - t(d+1)A.$$ We can therefore conclude that the order of $A$ is 8 if and only if $-d = 1$ and $t(d+1) = 0$, which since $t \neq 0$ are both equivalent to $d = 2$. Therefore, an invertible matrix $A \in GL(2,\mathbb{F}_3)$ has order 8 iff $\det(A) = 2$ and tr$(A) \neq 0$ (which we showed is necessary before). You'll notice that this agrees with the concrete examples given by Travis and Chris Culter.

We can use the same approach but reduce drastically the complexity of the system in the entries $a, b, c, d$ if we instead look for a square root of some matrix with order $4$.

The matrix $A = \pmatrix{0&-1\\1&0}$ satisfies $A^2 = -I$ and so has order $4$ over any field of characteristic not $2$. In particular, if we can find a matrix $B$ such that $B^2 = A$, then $B$ will have order $8$.

Writing $B = \pmatrix{a&b\\c&d}$, the condition is equivalent to the system \begin{align} a^2 + bc &= 0\\ b(a + d) &= -1\\ c(a + d) &= 1\\ d^2 + bc &= 0 \end{align} The second equation implies that $b = \pm 1$, and by negating the matrix (which preserves the property that $B^2 = I$) we may assume $b = 1$, and substituting gives $a + d = -1$ and $c = -1$. The first and fourth equations give that $a, d = \pm 1$, and then the third equation gives that $$a = d = 1 ,$$ yielding the solution $$\pmatrix{1&1\\-1&1} .$$

If you're curious to know all matrices having order $8$, that can be done by brute force. In Python:

# Returns True if m is the 2x2 identity matrix.
def one(m):
  return np.array_equal(m, np.identity(2))

# Returns the square of m, reduced modulo 3.
def square(m):
  return np.vectorize(lambda n: n % 3)(np.dot(m, m))

# Iterate over all 81 2x2 matrices with values in F_3.
for (a,b,c,d) in itertools.product(range(3), repeat=4):
  if (a or b or c or d) == 2:
    # Choose the +/- representative that starts with a 1.
    continue
  m = np.array([[a,b],[c,d]])
  m_2 = square(m)
  m_4 = square(m_2)
  m_8 = square(m_4)
  if one(m_8) and not one(m_4):
    print '\\pm\\pmatrix{%d&%d\\\\%d&%d},\\;' % (a,b,c,d)

This outputs $12$ solutions:

$ \pm\pmatrix{0&1\\1&1},\; \pm\pmatrix{0&1\\1&2},\; \pm\pmatrix{1&1\\1&0},\; \pm\pmatrix{1&1\\2&1},\; \pm\pmatrix{1&2\\1&1},\; \pm\pmatrix{1&2\\2&0} $