I'll try to give you the formalist perspective, which is a sort of 'minimal' take on the whole matter.

Everything starts with a set of symbols, usually finite, that can be combined to form strings called formulas.
Logic is then defined as two set of rules: one that tells you which strings of symbols are considered valid (morphology), and one that tells you which valid formulas follows from which valid formulas (syntax).

Then there's the concept of truth: when you have a logic, you notice that sometimes formulas refer to entities or states of some environment, and that syntactic rules somehow reflect processes happening between those entities.
Specifying which environment, which processes and which entities you are considering is the purpose of ontology, while the task of relating ontology and morphology/syntax is the purpose of semantics.

As you can probably imagine, there are a myriad of logics and myriads of ontologies (often called models).
There's Hilbertian ontology, where the environment is a set or a class, the entities are its members and relations and functions between them, and semantics relates Tarskian truths to other Tarskian truths.
There's categorial ontology, where formulas are interpreted as object of a category and syntactic rules as arrow between them.
There's dialogical ontology, where formulas are states of a game and rules are ways for attacking or defending the current state.
There is possible world ontology, which you have described.
And so on and so on.

Hystorically, a specific set of rules and symbols emerged exceedingly often, and seemed to be particularly apt to capture the reasoning that mathematicians intuitively adopted. That is now known as classical logic (CL), and for a very very long time it was believed to be the only "true" logic, that is the logic of the atemporal and universal description of all things.
CL is very useful and can be adapted to a wide array of ontologies: for example, Boolean algebras (which are instances of the Hilbertian ontology) and possible worlds semantics. The latter in particular was ideated for an extension of CL, both in symbols and rules, known as modal logic.

Enter probability.
The determination of which concepts the word refers to has a long and heated history, but now the modern understandig is four-fold. On one side, you have those who refer to a stated property of the world, a not very well specified "long-run randomized frequency" (frequentist). On the other side, you have those who believe that probability does not refer to an objective property of a system, but to a degree of beliefs of an observer (Bayesian). Bayesians themselves are divided among those who thinks that probabilities are entirely subjective (subjectivist), relying on the De Finetti coherence theorem and pragmatic interpretation, and those who thinks that probabilites are the degrees of belief that an idealized rational agent has about a system. These folks we can call objectivist, but since they are the majority here on LessWrong, it's simpler to just call them Bayesian.
Bayesians rely on Cox theorem, that justifies the structure of probability from a small set of minimally rational requirements.
All three of them, frequentists, subjectivists and Bayesians, believe that the structure of probability is correctly described by the mathematical concept of a measure, as formalized by the Kolmogorov axioms.

Enter Jaynes.
He was a physicist, and wrote a book from a Bayesian perspective, showing that probabilities thus intended are an extension of CL. Where CL can be seen as assigning to proposition only two values, 0 and 1, PTEL (probability theory as extended logic) actually relaxes that restriction, assigning values in the [0,1] interval, following two simple rules derived from Cox theorem.
In his work, Jaynes greatly systematized and simplified the field, solved many of its paradox and brought probability theory to previously unexplored areas of application. He also talked about the ideal rational agent as a 'robot', it is thus no surprise that his book is regarded as a cornerstone for LW's understanding of Artificial Intelligence.

Now, on to your questions:

Does the above explanation differ from how other people use probability?

As you can see, you are just using one ontology (possible worlds) to justify one interpretation (Kolmogorov measure), but there are many more. The interpretation of choice here is PTEL, usually coupled with an Hilbertian ontology for the underlying CL or just left unspecified.

why should those estimations follow the laws of probability?

Because of Cox theorem, you can show that with a specified amount of initial information, you can do no better than following the laws of probability.

And if I understand right, they says that Bayes' theorem follows from Boolean logic, which is similar to what I've said above, yes?

Actually no. First, there is no Boolean logic: there is classical logic interpreted in the ontology of Boolean algebra, but that doesn't really matter. Cox theorem is based on CL, but makes additional assumptions (that of a minimal, ideally rational observer). It's not just pure logic.
Also there has been some exploration in the direction of extending Cox with other basal logics.

I'm familiar with predicate logics as well, but I'm not sure what the interaction of any of them is with probability or the use of it

As per above, PTEL is based only on classical logic, which is a particular first order, two-valued predicate logic. AFAIK, no successful extension of Cox has been made to other kind of logic.
Fuzzy logic resembles PTEL in the expansions of the set of truth values, but uses different rules than CL, so the resemblance is only superficial: PTEL and fuzzy logics are two very different beasts.

sets just need to be exhaustive and mutually exclusive for the Kolmogorov axioms to work, right?

No, not really. Kolmogorov axioms are defined on any (sigma)-algebra, wether it is the algebra of subsets of a measurable sets or some other things.

the answer really is out there?

Of course it is ;)

*I keep seeing probability referred to as an estimation of how certain you are in a belief. And while I guess it could be argued that you should be certain of a belief relative to the number of possible worlds left or whatever, that doesn't necessarily follow. Does the above explanation differ from how other people use probability?

I believe you've defined an equivalent if unusual form (or rather, your definition can be extended to an equivalent form). You need the notion of the measure of a set (because naively it can be confusing whether one infinite set is bigger than another), and measure is basically equivalent to probability; "how certain you are of a belief" is equivalent to "the measure of the worlds in which this belief is true, relative to that of the worlds that you might be in now".

*Also, if probability is defined as an arbitrary estimation of how sure you are, why should those estimations follow the laws of probability? I've heard the Dutch book argument, so I get why there might be practical reasons for obeying them, but unless you accept a pragmatist epistemology, that doesn't provide reasons why your beliefs are more likely to be true if you follow them. (I've also heard of Cox's rules, but I haven't been able to find a copy. And if I understand right, they says that Bayes' theorem follows from Boolean logic, which is similar to what I've said above, yes?)

The only laws of probability measure I know are that the measure of the whole set is 1, and the measure of a union of disjoint subsets is the sum of their measures. I'm finding it hard to imagine how I could hold beliefs that wouldn't conform to them. I mean, I guess it's conceivable that I could believe that A has probability 0.1, and B has probability 0.1, and A OR B has probability 0.3, but that just seems crazy. I guess what convinces me is dutch-booking myself; isn't a dutch books argument precisely an argument that another set of probabilities would be more likely to be true?

*Another question: above I used propositional logic, which is okay, but it's not exactly the creme de la creme of logics. I understand that fuzzy logics work better for a lot of things, and I'm familiar with predicate logics as well, but I'm not sure what the interaction of any of them is with probability or the use of it, although I know that technically probability doesn't have to be binary (sets just need to be exhaustive and mutually exclusive for the Kolmogorov axioms to work, right?). I don't know, maybe it's just something that I haven't learned yet, but the answer really is out there?

I'm not aware of any flaws with propositional logic. If you reach a problem you can't solve with it then by all means extend to something fancier.

Those are the only questions that are coming to mind right now (if I think of any more, I can probably ask them in comments). So anyone? Am I doing something wrong? Or do I feel more confused than I really am?

I think you're trying to be too formal too fast (or else your title isn't what you're really interested in). Try getting a solid practical handle on Bayes in finite contexts before worrying about extending it to infinite possibilities and the real world.

*I keep seeing probability referred to as an estimation of how certain you are in a belief. And while I guess it could be argued that you should be certain of a belief relative to the number of possible worlds left or whatever, that doesn't necessarily follow. Does the above explanation differ from how other people use probability?

Probability is never used as a degree of belief. Likelihood is used as a degree of belief. See this thread: http://stats.stackexchange.com/questions/2641/what-is-the-difference-between-likelihood-and-probability

Once you understand likelihood it's easy to see why it represents degree of belief.