Step 1 - Representing shares in the company.
This is easy enough and has been discussed. The company sends a small amount of bitcoins to one of its addresses. It releases a digitally signed announcement that any bitcoins which can be traced back to this particular output are tokens representing shares in the company. When dividends are to be paid, they are sent (in normal bitcoins) to addresses which contain tokens in proportion to the amount. Initially the company is in ownership of its shares and can sell them to raise funds.
Step 2 - Enabling OTC trades.
Also easy. People who want to trade can broadcast their offers, perhaps on a dedicated Bitstock p2p network. People who want to execute standing orders can contact their issuers and together construct a Bitcoin transaction that sends X normal bitcoins from A to B and Y tokens from B to A, and both sign it. No trust is needed because the exchange happens simultaneously. There can be a Bitstock client that is a modified Bitcoin client, which is careful to distinguish tokens from normal BTC and can communicate with the Bitstock network.
Step 3 - Committing to offers.
Here's the hard part. With a normal OTC trade, there's nothing stopping a trader from backing out of an issued order if it becomes unprofitable by the time he is taken up on it. A market where orders needn't be honored will be inefficient and subject to manipulation. There needs to be some way to make committing orders.
One could conceive concocting some special Bitcoin transaction where the output can be claimed by reciprocating by sending tokens to a specified address, up to a given time. But I think this has too many moving parts to work. The Bitcoin script will need to verify that the tokens indeed originate in the company's address, and the completed transaction will expire if not included by some time - which is said to be impossible since it will be messed up in chain reorgs.
One way to do this is with a distributed trust model such as my own NodeBank proposal, where the bank nodes act as escrow for the trades.
If you want to do this completely trustless, I think you may have to create a separate Bitstock blockchain with its own rules (shared between all companies, but distinct from Bitcoin). I'm not sure it's possible to make a commitment mechanism for offering bitcoins for token bitstocks, so Bitstock will have to be its own currency which can also be used to create company tokens (just like Namecoin is a currency which can be used to create a DNS record). The Bitstock blockchain will have rapid blocks and a relatively strict timestamp requirement, and will be merge mined with Bitcoin. It will have a mechanism for making offers of Bitstock tokens vs. normal bitstocks, which is enforced by protocol if an execution request is made with its hash included in an early enough block. There should be a way to make special rules to make this survive reorgs - for example, orphan blocks will also be considered when evaluating whether an execution was given early enough, but a confirmation of this validity will also be included in the main branch, and require enough confirmations to make sure a validation can't be added retrospectively.
Step 4 - Continuous trade services.
No matter how clever we make the decentralized stock exchange, some things can still only be offered by a centralized service, in particular in regards to the speed with which orders can be placed, retracted and executed. A centralized service can be built on top of the p2p system to offer such features. It should enable depositing and withdrawing normal coins and token coins, and offer advanced features for trading deposited coins.