There is something like this described on the wiki.
Update: As Meni wrote in a comment below, this is more flexible than you require, since you already know who should pay, and how much.
So we can create a single transaction with 2 inputs, one from Alice and one from Bob, and a single output to the recipient of the payment.
Alice and Bob need to both have an input in their wallet of the right size, so we don't worry about who gets the change. Then Alice tells Bob what input she's going to use. Bob makes a transaction including both Alice's and Bob's input, and signs his input with SIGHASH_ALL, meaning that his signature isn't valid unless Alice also signs her input. He then sends the incomplete transaction to Alice for her to sign, she signs her input, and sends the result to the network.