Adding a new attribute to addresses in Magento is not trivial. The attribute needs to appear in all back-end address forms. The attribute needs to appear on the checkout and edit address forms for the customer. The attribute needs to be saved in the database when the user checks out.
There are several tutorials on the internet describing how to add attributes to the address, but I found that none of those tutorials led to a satisfying result.
I combined several of those tutorials into a new module. This module has been tested with Magento 1.7.0.2 and 1.6.1.0. The attribute works in the front-end, the back-end and is available trough the Magento API.
You will find the module in this Github repository. Read the README to find out how to use the module.
I intend to keep this module compatible with future versions of Magento. Please fork & pull if I lag behind.
Questions and comments can be posted below.