A counterfactual is a statement or question in the form 'If X ... would Y". Y would happen if X were true. Or, would Y be true, given that X were true? [0]
In the case of this puzzle, a counterfactual can be used to embed a question X within your question Y. By doing so (and exploiting the phrasing of the problem), you force the gods to answer in a manner that either reveals their identity as True, False, or Random.
Explaining the actual process through which the counterfactual is used to solve the problem is a bit tedious but the Wikipedia article on the puzzle has a pretty straightforward explanation of the reasoning[1].
