I wanted to add a message to orders when I did some auto approving of orders. To add some trace of that you need to load user which will be the one that did that. Send $values that will be used for token replacement in message and also select which message type you are going to use. In here I made a clone of default message "commerce_order_admin_comment" and used that. But you can use whatever you want and also its possible to create new type of message with code and "message_type_create" look more in example module in messsage module folder how to achive that.
$account = user_load("236242"); $values = array( 'arguments' => array( '@order_status' => 'Approved, by system', '@order_status_previous' => 'Pending' ), ); $message = message_create('commerce_order_admin_comment_auto', $values, $account); $wrapper = entity_metadata_wrapper('message', $message); $wrapper->message_commerce_order->set($order_item->order_id); $wrapper->save();