There is several ways to add order history, with less or more data
Quick way :
$message = 'Comment to add in order history'; $order->addStatusHistoryComment($message); $order->save();
With all informations :
$history = Mage::getModel('sales/order_status_history')
->setStatus($order->getStatus())
->setComment('Comment to add in order history')
->setEntityName(Mage_Sales_Model_Order::HISTORY_ENTITY_NAME)
->setIsCustomerNotified(false)
->setCreatedAt(date('Y-m-d H:i:s', time()));
$order->addStatusHistory($history);
$order->save();