Possibly they're both in the scouting party that capture the dwarves in Mirkwood? I mean that's the logical place for Legolas to show up, no?
I note she's dark haired, so being his sibling or other relation seems unlikely. Actually, what is the significance of elven hair colour? I gather it has something to do with which first age group from which they are descended? Does that mean everyone in the woodland realm should be blonde, or just the royalty/nobility?
...perhaps it's just as simple as they're the only pretty people in the whole trilogy.