I have not specifically tried this with related products, but the code below works with custom products, and I am sure that you can change it as needed to suit your situation.
$order = Mage::getModel('sales/order')->loadByIncrementId($this->getOrderId());
foreach ($order->getAllItems() as $item){
$productOptions = $item->getProductOptions();
if (isset($productOptions['attributes_info'])) {
foreach ($productOptions['attributes_info'] as $productOption) {
echo $label = $productOption['label'];
echo '<br />';
echo $value = $productOption['value'];
}
}
}
My suggestion is to start broadly (that is, at a level $item), see what Magento returns (using Zend_Debug::dump($item->getData()), and then work up to what you need.
Hope this helps.