Take a look at the UserProperties.Add method and the UserProperty object. The user will be able to edit any custom fields on the All Fields page of the standard contact form. For greater discoverability, you might want to implement a published custom form or, for Outlook 2007, form region.
Note that, although you can create a new text property, it is not possible to create a property that behaves like the standard telephone properties.