Here, some of my code to manipulate Magento product options.

Creation

You first need an array with the options you want to save

$values = array();
foreach($options as $option)
{
    $values[] = array(
        'title' => $option['name'],
        'price' => $option['price'],
        'price_type' => 'fixed',
        'sku' => $option['sku'],
        'sort_order' => $x,
        'is_delete' => '0',
        );
    $x++;
}
$newOption = array(
            'title' => "Public",
            'type' => 'drop_down',
            'is_require' => 1,
            'sort_order' => 20,
            'is_delete' => '',
            'previous_type' => '',
            'previous_group'    => '',
            'values' =>$values,
        );

Then add them to your product, I have seen a lot of different way to do it

$product->setCanSaveCustomOptions(true);
$product->getOptionInstance()->addOption($newOption);
//or
$product->getOptionInstance()->setOptions($newOption);

$product->getOptionInstance()->saveOptions();

$product->setHasOptions(1);
$product->setRequiredOptions(1);

$product->save();

or via OptionInstance

$optionInstance = $product->getOptionInstance();
$optionInstance->setOptions($newOption);
$optionInstance->setProduct($product);
$optionInstance->->saveOptions();

But it doesn’t work, I finally use this

$product->setProductOptions(array($newOption));
$product->setCanSaveCustomOptions(true);
$product->save()

To delete product options, there is several way too

$oldOptions = $product->getOptionInstance()->getOptions();
foreach ($oldOptions as $key => $option){
       $oldOptions[$key]['is_delete'] = 1;
}
$product->getOptionInstance()->setOptions($oldOptions);
$product->getOptionInstance()->saveOptions();

//or 
$optionInstance = $product->getOptionInstance()->unsetOptions();

But it doesn’t work too, so I use :

$options = Mage::getModel('catalog/product_option')->getCollection()->addFieldToFilter("product_id", $product->getId());
foreach($options as $option)
{
   $option->delete();
}

Some more informations:
To see options on admin, your product entity (table catalog_product_entity) should have attribute (column) has_options set to 1.
Options are saved in tables : catalog_product_option, catalog_product_option_price, catalog_product_option_title, catalog_product_option_type_price, catalog_product_option_type_title and catalog_product_option_value.