Thanks for the replies !
So i can make a transaction with 1 input and 2 outputs where the first one is the change and the other one is data with the op_return code. Sounds great !
Is there any consensus on the fees required ? Where can i find this information updated ?
Yes that is correct 1 in 2 out (OP RETURN+ change) is the most common. It can also be "combined" with a normal transaction to reduce cost so that would be 1 or more inputs, plus 1 or more "paying" outputs (including change) plus the OP_RETURN. Fee shouldn't need to be more than any other transaction. The minimum is 1,000 satoshis per KB. If you upgrade to v0.10 of the client there is an RPC call which estimates the fee required to be quickly confirmed. It can be used for any transaction (including those with OP_RETURN outputs).
In the past this was done by dumping the data into a "normal" output which would be unspent. Please don't do this as the network has no way of knowing that output is "fake" and thus it remains in the UTXO set forever. OP_RETURN allows you to create an output which is included in a block but is marked as unspendable thus not bloating the UTXO (a more critical resource often ignored by most).
Three important points to consider about OP_RETURN:
1) More than one OP_RETURN output in a transaction is
invalid non-standard (and won't be relayed by most nodes).
2) A "payload" of more than 40 bytes in the OP RETURN output is
invalid non-standard as well.
3) Any value assigned to the OP_RETURN output is unspendable so the "coins" are effectively destroyed. Unless you intentionally want to destroy some coins, you should ensure the OP_RETURN outputs always have a value of zero.
Some additional info:
http://bitcoin.stackexchange.com/questions/29554/explanation-of-what-an-op-return-transaction-looks-likeOn edit: Thanks Gavin for non-standard vs invalid and routine counting correction.