Update customer gender translations

The gender attribute is a dropdown attribute like any other one. Its labels are stored in the table eav_attribute_option_value.
But since there is no (out of the box) way to manage from the backend the customer attributes I see 2 options here.

Option 1. Quick and dirty:
Change the options in the template.
Copy app/design/frontend/base/default/template/customer/widget/gender.phtml to your theme and add after

 <?php $options = Mage::getResourceSingleton('customer/customer')->getAttribute('gender')->getSource()->getAllOptions();?>

this:

<?php foreach ($options as $key => $option) : ?>
    <?php $options[$key]['label'] = $this->__($option['label']);?>
<?php endforeach;?>

Then you can translated the values like any other string.

Option 2 - Long but clean.
Insert into the table eav_attribute_option_value the values for your second (and third and so on..) store view.

I said that this is the 'clean' version.
The theory it's clean but the solution I have it's not that clean.

Identify the attribute id:

SELECT * FROM eav_attribute where attribute_code = 'gender';

Let's say it's 1000.
then identify the options for the attribute

select * from eav_attribute_option where attribute_id = 1000;

Let's say you get 100 and 101.
Then look in the eav_attribute_option_value to see which is which.

select * from eav_attribute_option_value where option_id in (100, 101);

now you will see which is the Male option and which is the Female option.

Let's say 100 => Male, 101=>Female.
Now insert your values for the second store store.

Insert into `eav_attribute_option_value` set option_id = 100, store_id = 1, value = 'Translation for Male here'; 
Insert into `eav_attribute_option_value` set option_id = 101, store_id = 1, value = 'Translation for Female here';

Sorry but I don't have an upgrade script version for this.

I would go with the quick and dirty one. Fewer headaches.