Whitney Hess sums it up best for me in her article here: http://whitneyhess.com/blog/2012/09/17/how-to-evaluate-a-ux-designer-for-your-company-or-what-makes-a-great-user-experience-designer/

Even though she specifically talks about UX designers, I think it applies more generally. I tend to look for someone's approach, their philosophy, and the fact that they actually have opinions. The fact that they offer suggestions for improvements instead of mindless praise for the product I'm working on, and that they have the backbone to disagree with me even in their interview process. Obviously, there is a certain bar for execution that must be met, but that's the easy part to nail down.

I want a wealth of stories about their design work.

"This worked initially but once we did x we had to change it to look more like this."

I want to know that they had a hypothesis for why they designed what they did - and that they reacted to feedback/usage and kept moving forward.