I posted about this in relation to Drupal 5 here. Now it's time to do this with Drupal 6...
Let's recap: Node reference field allows you to add a link from one content item to another. You add the reference to another existing node when you create a node with a nodereference field. The node being referenced must exist in order for this to work.
This bit of code lets you reference a non-existent node. The referenced node is created when the validation fails to find an existing node.
Some very basic code is attached. To try this, put the two files in a folder in your site modules folder. (see attached files). This code has been tested with Drupal 6 and CCK 2.
Update: The download was removed from this page as someone else took the code I provided and create a Drupal.org project for it.