That is a specific, and challenging, problem.
There are two kinds of phone directories.
1) XML-Based Server Directories - these are common in higher-end (and very low-end) phones like the Cisco 7900 series. You write an application on the server that interacts with the phone's connection to the system and build the directory "more or less" on the fly and report it back to the phone.
2) Phone managed contact lists - these are harder to manage from the server, since the update mechanism is usually proprietary and may require a phone restart or data reload to get them working.
The type of phone will determine the type of update you'll need to do, and that usually falls outside the scope of what FreePBX supplies.
What kind(s) of phones do you have? Perhaps someone with more experience in your phone can provide some insight. My experience is largely with Cisco phones running in SCCP mode and POTS phones through DAHDI.