Hi there,
As far as I know, the incremental search on a look up column will only kick in when you have more than 20 items in the lookup list.
I'm not sure how you're going to be able to make it easy for them to add to the lookup skill list. Easiest and least troublesome would be to just add a link to the EditForm.aspx:
<a target="_blank" href="http://site/lists/skilllistname/NewForm.aspx">Skill not here? Click here to add it!</a>
The target="_blank" is so that the add new item form is opened in another window. Though... Your initial form will still have to be refreshed which means they'll lose everything they've filled in so far.
Is your lookup column set to allow multiple items select? Because then it's another ball game too.
Sean
May your PC's be fast and your restarts few.