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();