Looking for someone who will use CiviCRM day-to-day (as opposed to a CiviCRM developer or consultant), how do I maximize the chance that they'll succeed in their job and in using CiviCRM?
Even as CiviCRM is a key tool for many roles at an organization, it's often an afterthought in choosing the best person for the job. Selecting someone who knows CiviCRM will certainly help, but it's also good to hire someone with the capacity to learn the way your organization applies CiviCRM to its work.
Stuart Gaston did a fabulous session at the 2014 CiviCRM User Summit called Hiring and Training for Success. He highlighted ways to think about individuals' patterns when they encounter technical problems and interview questions (like "What is your favorite Excel trick?") that help in highlighting those. Even just reading the slides is a good place to start thinking.
It's good to list CiviCRM as an element of the job and a bit of experience that would be valued, but you probably don't need to make CiviCRM experience an absolute requirement.
However, you can maximize your chances at finding experienced CiviCRM users by posting on CiviCareers, the CiviCRM job board. Posting is free, and you'll maximize the chances of finding someone who can quickly understand your CRM and maybe even share tips from past work.
(Full disclosure: my coworkers and I started CiviCareers after a series of conversations at DC CiviCRM meetups where people laid off from a local organization were looking for jobs where they could apply their CiviCRM experience. It isn't a commercial venture--it's free and always will be--but it does mention that it's hosted by AGH Strategies.)