Adding basic support for Node Reference fields to the Feeds module is
pretty straightforward (if you don't worry too much about the advanced
features of nodereference).
In fact, it's almost a direct copy of the existing support for basic CCK field
types. Just check for a different field type (line 19) and lookup the nid
based on the GUID from the feed (line 51).
I've used a CSV file with a quoted, comma-separated field containing GUIDs of my target nodes and explode the value using Feeds Tamper.
To "install" this code, just drop nodereference.inc into the feeds/mappers/
directory and clear your Drupal cache.