Nonclustered Index in SQL Server

So, I've run into an issue with one of my queries because it takes about 40 seconds to run and according to the Recent Expensive Queries section of the Activity Monitor in SQL Server, there is a section of code taking up about 51% of the query. 

First, let me say that I've been writing Transact SQL for quite awhile but have never ventured into the Clustered and NonClustered areas of forming Indexes.  I do use indexes on all my tables but that's just the regular Primary Unique key. 

We've been using this query for awhile and it does work but when the result set is about 5K records it takes a little while to run.  So here's the actual query itself

SELECT 
    PartNo, 
    SerialNo, 
    HeciCode, 
    ScanDate, 
    OrderType, 
    PoNo,  
    po.IssueDate, 
    SoNo 
FROM ScanHistory sh WITH (NOLOCK) 
LEFT OUTER JOIN trkRWPOHeader po WITH (NOLOCK) 
    ON sh.PoNo = po.PONum 
WHERE len(PoNo) > 2 
    AND ScanDate > '1/1/2009' 
    AND PartNo = 'RDH102472' 
    AND sh.SerialNo NOT IN (SELECT SerialNo 
                            FROM ScanHistory WITH (NOLOCK) 
                            WHERE PONo = '' 
                                OR (OrderType = 'SO' AND SoNo = '000001') 
                            ) 
    AND sh.SerialNo NOT IN (SELECT i.SerialNo       
                            FROM skp_SkidItem i with (nolock) 
                            INNER JOIN skp_Skid sk with (nolock) 
                                ON i.SkidNo = sk.SkidNo 
                            WHERE sk.SkidStatus = 'Shipped' 
                                or i.ItemStatus = 'Shipped'
                            ) 
ORDER BY PoNo

When you look at the recommended Execution Plan it says:
Missing Index (Impact 51.4221): CREATE NONCLUSTERED INDEX [<name of missing index, sysname,>] ON dbo.ScanHistory (PartNo, ScanDate)

I have posted this issue on Stack Flow and I have had some responses but nothing really makes sense at this point.  I've tried the above suggestion using a dummy missing index but that didn't seem to work.  Anyhow, if any of you are expert Transact SQL programmers I would love to hear from you on any suggestions or just general explanations on Nonclustered Indexes.

Thanks!