1. Submit transaction A to miners
2. Submit another transaction B (spending the same coins as A) to the vulnerable merchant
3. This is the really hard part: make sure that the merchant doesn't know about transaction A until you got your purchase and ran away.
If the merchant has good network connectivity, it is very, very hard to perform this attack successfully, certainly not something that would be done to get a free newspaper or coffee.
I just dug up an interesting and relevant bit of history. Here is, to my knowledge, the very first response, ever, to the original bitcoin proposal on the cryptography mailing list:
http://www.mail-archive.com/cryptography@metzdowd.com/msg099...
"For transferable proof of work tokens to have value, they must have monetary value. To have monetary value, they must be transferred within a very large network - for example a file trading network akin to bittorrent.
To detect and reject a double spending event in a timely manner, one must have most past transactions of the coins in the transaction, which, naively implemented, requires each peer to have most past transactions, or most past transactions that occurred recently. If hundreds of millions of people are doing transactions, that is a lot of bandwidth - each must know all, or a substantial part thereof."
So it appears the timeliness of verification on a large scale was possibly the very first concern ever voiced about bitcoin.
In practice you may find that your starbucks coffee will take 10 minutes to buy with a newly created wallet, but comes in immediately when paid with a wallet that you've been using for a while (so it has a 'reputation').