As people have already observed, if G is cyclic and g is a generator, then the answer is always "yes". Steven Sam's comment shows that there can't be a uniform algorithm that works for all cyclic groups Z/n. In fact, the problem is undecidable for any given n. For instance:-

For finite cyclic G of order n with generator g, the question can be rephrased as "Is it decidable whether the element h is of finite order dividing n?". Suppose H is torsion-free. If this problem is decidable for some n then the word problem is solvable in H.

But the word problem is not solvable in torsion-free groups. For instance, Collins and Miller constructed a sequence of presentations for torsion-free groups H_1, H_2,... with the property that each H_i is torsion-free and it is undecidable which of the H_i are trivial. (More precisely, the set of all i such that H_i is trivial is recursively enumerable but not recursive.)

As people have already observed, if G is infinite cyclic and g is a generator, then the answer is always "yes". Steven Sam's comment shows that there can't be a uniform algorithm that works for all cyclic groups Z/n. In fact, the problem is undecidable for any given n. For instance:-

For finite cyclic G of order n with generator g, the question can be rephrased as "Is it decidable whether the element h is of finite order dividing n?". Suppose H is torsion-free. If this problem is decidable for some n then the word problem is solvable in H.

But the word problem is not solvable in torsion-free groups. For instance, Collins and Miller constructed a sequence of presentations for torsion-free groups H_1, H_2,... with the property that each H_i is torsion-free and it is undecidable which of the H_i are trivial. (More precisely, the set of all i such that H_i is trivial is recursively enumerable but not recursive.)