Just say you make a prediction and broadcast it to a network of nodes by spending a coin which confirms your transaction and thus embeds the prediction in a block chain....the coins go to the miners of the block chain to incentivise mining it. Any node could see any prediction and people could setup "prediction exchange clients" you could install that possibly interacted with bitcoind.
Biggest issue I can see would be publishing/grading of predictions. A block-chain based trust/reputation infrastructure could allow for self-grading with users without a history of honesty paying much higher premiums.
Governments would never allow a prediction market using centralised infrastructure so this gets around it. Good/bad or ugly idea ?
I guess it depends on what you're predicting, but I suspect that
Intrade provides evidence that governments are fine with allowing prediction markets using centralized infrastructure. Hell, betfair and the other betting exchanges are arguably prediction markets and there's only really one government I can think of that has a major problem with them.