Yep. For the ones I've looked into, orders match when they sum to $1. Eg, I bid $0.75 on yes and you bid $0.25 on no. The contracts are very carefully written such that they are mutually exclusive, only one of us gets $1 when the contract resolves. And like you suggest, you pay a fee on the way out.
If this is the case, it kills me that online poker is still illegal federally. Zero sum skill game minus fees.
The issue here is that "skill game" is something that lawyers would have to prove to judges.
Is it technically possible to encode a whole game of hold’em using one of these markets?
That's called parimutuel being and the broker just takes a vig (vigorish). It's analogous to agency based trading in finance.
The broker can also set the odds and act as a market maker, like principal based trading in finance.