Basically, start off with some random data, hash it, and publish those hashes ahead of time in public (like the blockchain, or in the page itself like MyriadCoins.) Then use the random data and bet data (optional) as inputs to a cryptographically-strong hash during the game to get a randomly distributed output. Release the random data after some period of time after the game, so users can verify it.
The strength of this comes from the strength of the hash functions used (very good assuming lots of entropy in the random data) and the security of the random data up to the point where it is used (depends on your development skills, and hax0rs.)
Also, if you haven't yet, read up on how SatoshiDice implements the verification - it is a good writeup.
If you are talking about other games, like proving a sports bet was paid out fairly, that's a whole other topic...