Well, that would certainly depend on which "god" and prophet you were referring to. The Christian God has made it very simple: see if the prophet's prophecies are actually fulfilled. Old Testament prophets usually prophesied of things soon to come, before prophesying of long-term events. Thus, Joseph, not strictly a prophet, but gifted with the ability to interpret dreams, foresaw 7 years of abundance followed by 7 years of hunger. You simply had to wait 8 years to see whether or not he was legitimate.
To turn this into a more generic answer. The best way of establishing the legitimacy of a prophet is to test whether his prophecies are fulfilled. A good rule of thumb may be that a legitimate prophet will be direct, non-contradictory and unambiguous. So a prophecy like "next year this time, there will be war" is probably true, or at least can be tested quite easily. While something like "the serpent will shake its tail twice and then the hidden grapefruit will spill over the onyx throne" is probably horse-pucky.
If a "god" takes the trouble to send a message, it would probably be easy to understand.