Magento allows saving multiple address for a customer. So you don't need any changes on database.
If you want to save address during checkout just do it like. Assuming your customerId is 10, you can save shipping address in following way:
$customerId = 10;
$addressArray = Array('prefix' => '',
'firstname' => 'Firstname',
'lastname' => 'Lastname',
'suffix' => '',
'company' => 'Company',
'street' => array('Address1', 'Address2', 'Address3'),
'city' => 'City',
'region' => 'State',
'country_id' => 'cc',
'postcode' => 'ZIP',
'telephone' => 'PhoneNum',
'fax' => 'FaxNum');
$shippingAddress = Mage::getModel('customer/address')
->setData($addressArray)
->setCustomerId($customerId)
->setSaveInAddressBook('1');
$shippingAddress = $quote->getShippingAddress()
->setShouldIgnoreValidation(true)
->addData($shippingAddress);
You can loop above code for different address. If this address is your default shipping, you can make it default by following code:
$addressArray['is_default_shipping'] = 1;
Good luck!