Ranking skills depending on similarity
Pretty late but I'm surprised this wasn't answered more.  "Cosine similarity" is a great technique to try, though simply letting users search with a hard string and then ranking by popularity isn't so bad (e.g. "dutch" brings up everything with "dutch" in it, though I would discard mid-word matches, so "ball" wouldn't return "football", but would return "ball room dancing").  

I'd say in any approach a main issue will be deduplicating previous (non-standardized) skills input by users that weren't quite standardized.  You could also try replacing the candidate skills with versions that have different synonyms substituted at search time, e.g. "soccer coaching" might be stored also as "football coaching" if most of your content is from Europeans.

Sometimes extreme accuracy might not be the best goal, though... You may want to encourage users to explore new skills that they never knew existed!  Not sure what your needs are...

Whatever you settle on, it might be worth building a semi-hand-crafted test set of queries and relevant results so that you can see if the performance is terrible (Google precision and recall in the context of search results).