The CDS market works similarly to any other market: traders announce prices (privately or otherwise) at which they are willing to trade, and if two traders' levels agree, a trade may be executed. These levels may be informed by quantitative models, gut feelings, even sheer necessity - but the mechanism by which trades are conducted is quite straightforward: two CDS traders agree to a trade, at which time their respective firms enter a legally binding contract to exchange the necessary cashflows. That part takes place off the desk, however.
There are two predominant forces in the CDS markets - again, as with most markets - the "buy side" and the "sell side". The buy side refers to those traders looking to place directional bets; they look to trade securities as advantageous prices, hold them for some time, and then sell them at a profit. The sell side, by contrast, is not interested in taking risk; it merely wants to service the buy side and be compensated for doing so. To accomplish this, sell side traders seek to simultaneously buy and sell the same security, capturing the difference in price for themselves and taking no exposure to the security in the process. The market dynamics arise out of this tension - buy side traders looking for "good" prices, and sell side traders seeking to capture a "bid ask" spread. Increasingly, however, sell side traders are starting to resemble the buy side as banks take on proprietary risk (evidenced most recently by Goldman Sachs).
It would appear that most of the regulatory concern with the CDS market is not about *how* contracts are traded, but rather the management of those contracts themselves. The CDS market is an "over the counter" (OTC) market, meaning transactions are executed between two consenting parties rather than via an anonymous exchange. In any OTC market, there is an advantage in being "the counter" - or the sell side. This is because the sell side 1) has an information asymmetry in that they see much more of the market than any individual buy side trader and 2) can adjust their price - even away from the "fundamentally correct" price - to take advantage of the supply or demand they perceive in the wider market. Thus, one of the first regulatory aims is increased price transparency.
A second concern is how each trader's firm treats the contract after it has been traded. AIG was not required to post collateral on their sold CDS, and consequently was ruined when they discovered they had sold more contracts than they had collateral to back them. Lehman's bankruptcy locked away funds owed to other firms, because they did not only have exposure to the firm they traded CDS *on*; they had exposure to the firm they traded *with* as well. The regulatory solution to the issue of counterparty risk is to create a CDS clearinghouse, which will standardize all collateral disputes and decrease counterparty risk throughout the market.
Finally, people are afraid that CDS are mathematically complex, difficult to price products - and to an extent they can be. Nonetheless, this fear arises with many derivatives, because they do not trade on an open market and do not represent "pure" parts of the capital structure (as if companies only issued simple stock and bonds in the first place). A response would be that having a mathematical grounding should actually increase people's faith in receiving an honest price, for in the absence of a highly liquid market, how else can you determine whether a price is fair? Thinly traded stocks may jump tens of percents each day, because there is no price discovery mechanism - and without a grounding in transparent math, who can say what the proper level is? Unfortunately, many attempts to explain CDS veer into complex math simply because they can, not because they need to. CDOs, while more complex, have a similar problem (though I recently tried my hand here).
I believe that these three items: OTC, counterparties, and scary math have greatly contributed to the demonization of CDS contracts. As Petrobull stated, the incestuous nature of many trading desks and sometimes-difficult trading vocabulary only add to the confusion. Moreover, we have seen the concrete and disastrous toll that derivatives can have in AIG and Lehman, among others, cementing (or necessitating the invention of) the error of these market's ways in our collective psychology.