Lewis held that possible worlds exist exactly like this one. His view entails that there are uncountably many things that exist in "uncountable infinities of donkeys, protons and puddles, of planets very like earth... small wonder if you are reluctant to believe it." Actualist possible worlds tries to use the power of modal logic using actual objects to ground talk of possible worlds. Actualists reject Lewis's view precisely because it is unbelievable.
There are at least three versions of actualist possible worlds semantics. According to Stalnaker, possible worlds are uninstantiated properties. Like the property of being a unicorn, the property exists even if there are no examples of unicorns. In logic-speak, an instance of the property is its instantiation. So uninstantiated properties are properties that nothing has. But for many philosophers, like Plato, the property can exist even if there is no instance.
Alvin Plantinga holds that possible worlds are complete states of affairs. These exist as abstract entities and have properties. The state of affairs "Quine's being a philosopher" has the property of obtaining, while the state of affairs "Quine's being a politician" has the property of not obtaining. Some states of affairs have the property of being possible, and others do not (though Plantinga does not state whether he thinks the imposible states of affairs non-the-less exist). Plantinga has a technical way of defining complete, but basically, for any state of affairs S, a complete state of affairs either includes either S or not S.
According to Robert Adams, possible worlds are not states of affairs, nor abstract objects, but complete, consistent sets of propositions. Propositions are actual intensional abstract entities, and these propositions have the property of being either true or false. A proposition like "Aristotle is tall" contains both the individual Aristotle and the property of being tall. Consistency in complete sets of propositions is inherently modal: It is consistent if it is possible to be true together.
Other philosophers will use a logical notion of consistency, ie, it is consistent iff there is a model which satisfies the set of sentences which mean the propositions. In such a case, anything that is logically consistent is possible, and vise versa. Adams was trying to avoid that conclusion. But the more empiricist philosophers (Hume, Quine, Carnap, early Wittgenstein) all accept that kind of view.
Finally, there are the fictionalists: possible worlds are fictional entities. Just as there are truths about Superman, fiction can ground truth. Just as the fiction of the ideal gas law gives us important truths, so fictional truths can be important. Talk of possibility is grounded on these kinds of important fictions. David Armstrong (not the one at McNeese) holds this kind of view, and cites Wittgenstein as his inspiration.
So possible worlds are: complete consistent states of affairs, complete consistent propositions, complete consistent sets of sentences or made up entities, each version grounding the truth of our modal claims and justifying modal logic.