1) create an unsigned Bitcoin transaction that pays 1 BTC from Alice to Bob
2) create an Ethereum address (smart contract) that can be redeemed either a) by Alice using a signature for a pubkey specified by Alice in advance, plus an secp256k1 (Bitcoin) signature over the hash of the Bitcoin transaction or b) by Bob after a timeout (e.g. 7 days)
Bob sends the number of ethers he wants to pay for 1 BTC to this Ethereum address/contract, and if Alice takes the offer she will redeem this amount, thus revealing the signature for the Bitcoin transaction, which Bob can then publish and get his 1 BTC.
Ethereum uses the same signature algorithm; you can sign arbitrary data from Ethereum's javascript library and check it from a contract.
https://ethereum.stackexchange.com/questions/2256/ethereum-e...
https://ethereum.stackexchange.com/questions/710/how-can-i-v...
You're pretty much stuck trading ETH and ERC20 tokens with those. Another technology coming is atomic swaps for transfers between chains.
For actual fiat the only decentralized option is stuff like localbitcoins. That's ok for small occasional trades but it's physically risky for large trades and legally risky for frequent trades.