Currently, to choose the date a post is published, one selects from a dropdown and modifies text fields.

For this task, enhance the existing system so that when users edit the publication date, a calendar pops up that allows one to easily page through months and select the day and time for the publication.  For a rough idea of the behavior, see travel sites such as kayak.com that allow users to select airline tickets with such popups.

Please note that any third-party calendar app you use must be compatible with WordPress's GPL license, and if it has a third-party JavaScript dependency, it should be one that WP already has in the admin, such as jQuery's.