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