What is the order of $2$ in $(\mathbb{Z}/n\mathbb{Z})^\times$? Is it there some theorem that makes a statement about the order of $2$ in the multiplicative group of integers modulo $n$ for general $n>2$? 
 A: Let me quote from this presentation of Carl Pomerance: 
[...] the multiplicative order of $2 \pmod n$
appears to be very erratic and difficult to get hold of.
The presentation describes, however, some properties of this order. The basic facts have already been elucidated by @HagenvonEitzen in his comment.
A: As others have pointed out, this is not trivial in the slightest. There are a few things you can find out, as  Hagen von Eitzen pointed out in the comments. I created the following plots for $n\in 1\ldots 1000,~~~~~ 1\ldots 10000, ~~~~~1\ldots 100000$. 



There are certain things from this picture that are easy to make sense of, notably the highest line, which is $y = x-1$ and then the other prominent lines for small divisors of $n-1$. I am intrigued by the few points that lie between $n-1$ and $\frac{n-1}{2}$. 
The first few elements of this appear to be:
$$9,25,27,81,121,125,169,243,361,625,729,841...$$
Which are all powers of prime numbers, which makes sense. This is actually A108989, and these are those non-prime numbers $n$ for which the multiplicative order of $2$ modulo $n$ is $\phi(n)$. 
I've also tallied the most common orders for the first $1,000,000$ odd integers and the first few were: 
$$\{2, 155171\}, \{4, 108716\}, \{8, 73643\}, \{12, 67834\}, \{6, 57771\}, \{1, 
  55868\}, \{16, 46866\}, \{24, 45317\}, \{48, 31026\}, \{32, 23299\}, \{36, 
  20669\}, \{96, 16278\}, \{72, 15858\}, \{20, 14476\}, \{10, 13413\}$$
See what you can make of that, it isn't in the OEIS. 
A: In general it is hard to say something about the order of an integer $a$ modulo $n$ (such that $a\neq -1$ or a perfect square) as $n$ varies. You may be interested to read about Artin's conjecture on primitive roots.
Essentially copied and pasted from the wikipedia article:

For example, take $a = 2$. The conjecture claims that the set of
  primes $p$ for which $2$ is a primitive root (i.e., those primes such that $2$ has the largest possible order modulo $p$, that is, $\text{ord}_p(2)= p-1$) has density
  $C_\text{Artin}=0.373955\ldots$. The set of such primes is (sequence A001122 in OEIS) $$S(2) =
 \{3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139,
 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373,
 379, 389, 419, 421, 443, 461, 467, 491, ...\}.$$ It has $38$ elements
  smaller than $500$ and there are $95$ primes smaller than $500$. The ratio
  (which conjecturally tends to $C_\text{Artin}$) is $38/95 = 2/5 = 0.4$.

