If it were me doing this project,
I would start out by looking at pre-made
PHP/MySQL scripts that would handle a
phone directory database type thing.
http://www.hotscripts.com/
Look at the various features, and what types
of scripts are available. Some may be free, others not.
I would then look at the possibilities of maybe
using Drupal or Joomla instead of a pre-made script.
My First Step therefore, is to get the PHP/MySQL
backend put into place. You need a database for
storing all of the information ... that is priority #1.
Once you have a database, any PHP script can access
it and render your pages, based off of templates or whatever.
It would be cool to focus some of your energy on small scale
rendering for mobile devices (search Google for that).
A Physician database via cell phone might be a good selling tool.