I think first of all he should have good knowledge of search engine marketing basics. He needs to understand what exactly is client looking for? their goals and manage the strategy accordingly.

Along with basic on-page and off-page optimization, he needs to think outside of the box and must have qualities of reverse engineering...

I agree with stephen somewhat, ability to optimize web page components is mandatory. Good writing skills helps. Web pages need to captivate the Internet visitor and convince the search engine that content is unique, authentic and intelligent. I don't worry much about off-site optimization as most of that is best left to occur naturally, as a reasult of exceptional content. You can always create your own off-site ranking factors should your internal linking structure be weak (do to lack of webpages).

A good search engine optimizers satisfies three things simultaneously: the Internet visitor, the web site owner and the search engines. This is why innovativeness (out-of-the-box thinking as steven refered to) is essential.

I would also add that this professional should have a strong curiosity to keep up with trends, best practices, and with case studies of what other businesses have know that worked and did not worked. This way, the professional can have an arsenal of knowledge that will lead the recommendations to a higher level of effectiveness.

Very good point.

That could also mean actually reading other people's SEO blogs and participating in search engine optimization forums, keeping updated on the search engine content guidelines and any other opportunity to find ways to adopt and develop effective optimization techniques.

Thanks everyone. Although I am putting less premium on the content creation for now as I am going to be handling that as I have been a marketing content creator for most of my career. Are there any topics for discussion that I can use to make sure that they candidates are not harboring black hat tendencies or will that be something that I will have to monitor over time? I know that seems like an odd question but I am trying to cover all bases.

Well, for a trendy starters, if they tell you how important incoming links are to your web page ranking and that's they're the world's best link schemers, then that's a good indicator of someone unable to perform search engine optimization and focused on manipulating the search engine.

Thanks for that tip. Although to be honest, is someone used the term 'schemer' to describe themselves I would be showing them the door!