There is more than one approach. One is to put a button with a label such as "add new" next to popup menu field that performs a script to create the new record in the appropriate table and then enter the correct info into the popup field to show the newly added value.
It's also possible to include "action values" (my term for this) in the value list that a script performed from a script trigger on the field detects and when detected, removes the action value from the popup field and performs the corresponding action (such as adding a new record) instead.
for a working example of "action values", see "Adventures in FileMaking #2 - Enhanced Value Selection". One of the early examples in this file demonstrates this technique.
Yes, my first inclination was to add a "add new" button, since I can tackle that pretty well. But this is someone else's solution, and I was trying to help him solve this problem. I found it useful for my own solutions as well, if there is an elegant way to do it. I'll check out the article, and report back with my findings.