I manage a data science team and revamped the hiring process pretty substantially about a year ago, to good results. Nothing in here is particularly original, but here's what we do:
1. Break down "data science" into several different roles–in our case, Analyst (business-oriented), Scientist (stats-heavy), Engineer (software-heavy). Turns out that what we mostly want are Engineers-Analysts, so our process screens heavily for those.
2. Figure out which types of people can be trained to be good at those roles, given the team's current skillset. I opted to look primarily for people with strong analysis skills and some engineering.
3. Design interview tasks/questions that screen for those abilities. In my case, the main thing I did was make sure that the interviews depended very little on pre-existing knowledge, and a lot on resourcefulness/creativity/etc. E.g. the (2-hour) takehome is explicitly designed to be heavily googleable.
4. Develop phone screens that are very good at filtering people quickly, so that we don't waste candidates' time. By the time someone gets to an onsite interview on our team there's something like a 50% chance they'll get an offer.
On the candidate side, when I'm applying I try to figure out first and foremost what a company means by "data scientist", usually by networking & talking to someone who already works there. This filters out maybe 90% of jobs with that title, and then I put more serious effort into the rest.