How do you get possible candidates for primitive roots of 12? 
Candidates for primitive roots are 1, 5, 7 and 11. $\phi(12)=\phi(2^2)\phi(3)=4$.
  $ord_{12}1 =1, ord_{12}5 =2, ord_{12}7 =2, ord_{12}11 =2$. None of these has  $\phi(12)=4$, thus number 12 has not primitive root. 

My question still remains: How do you get possible candidates for primitive roots? What about when trying to find primitive roots of some prime, how you get then possible candidates for primitive roots? 
 A: There are primitive roots modulo $m$ iff $m$ is $1, 2, 4$, a power of an odd prime or twice a power of an odd prime. Once you find a primitive root modulo a prime $p$, it is easy to find a primitive root modulo all powers of $p$. So the real problem is the case $m$ prime.
There is no general method for finding a primitive root. See
http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots. However, once you find one, call it $g$, then all other ones are $g^k$ with $k$ coprime with $p-1$.
The least primitive root is generally small. See http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Order_of_magnitude_of_primitive_roots
A: A primitive root exists, i.e. $\rm\:(\mathbb Z/n\mathbb Z)^*\:$ is cyclic, iff $\rm\:n = 2, 4, p^k, 2\:p^k\:$ for an odd prime $\rm\:p\:.\:$ Generally there is no better way to find a primitive root other than brute force: e.g. sequentially test small candidates, verifying that they have the desired order. This usually succeeds quite quickly since e.g. by GRH the least primitive root mod $\rm\:p\:$ is $\rm\:O(\log^6\:p)\:.\:$ See the Wikipedia page for more. It's always a good idea to check there first before posing questions. 
There are also very interesting conjectures about primitive roots such as Artin's conjecture. To learn about this and related topics I highly recommend reading Daniel Shanks: Solved and Unsolved Problems in Number Theory, 4ed, 1993, where you will find many expositions on how to make conjectures in number theory. It is essential reading for a budding experimental number theorist. Be sure to get the final $4$th edition (1993), which has much added content, esp. on making and judging conjectures.
More generally you may find of interest Andrew Sutherland's 2007 MIT Thesis Order Computations in Generic Groups. 
