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].

[0] http://en.wikipedia.org/wiki/Counterfactual_conditional [1] http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever.