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.