The objectid is the GUID of the record that the note is associated with and the objecttypecode is the entity code. The import utility can look up the regarding name; however, if you have mutiple accounts or contacts with the same name, this can get tricky and you may need to add the guids of the accounts.
This is much easier with Scribe Insight (www.scribesoft.com) as you can customize lookup steps to easily map the notes regarding record to the note.
You said that you didn't see a field on the notes table that indicates who the note belongs to. That is because you are looking at the table, which only has part of the leads fields. Look at the filteredannotation view to see all of the lead fields.