The answer is, as usual, "it depends". JeffE provides a perspective for a top US research university (Research, research, research, recommendation letters, research, baked beans, and research.). In my lab (small-but-good swiss university) PhD admission certainly works a bit differently.
First a bit of context: our lab usually consists of less than ten members, 2 of which are professors and one to two more being postdocs. We select our PhD students ourselves (there is no department or faculty-level hiring). Hence, PhD student selection is not something we do all the time.
Generally, the single most important factor for hiring for us is whether we already know the candidate. Broadly, potential students come in four tiers:
- Tier 1: students that we personally know to be good, for instance because they have done courses or their thesis with us. This means that we mostly hire from our own university, but as I only moved recently from a different university, we currently also like to hire from my old institution. Generally, if you know somebody in the lab (even other PhD students) and the other person vouches for your qualities, you are almost certainly in.
- Tier 2: students that people that we know know. If we need a position filled but don't have a strong internal candidate at the ready, we reach out to our personal networks. Usually, we don't cast the net particularly wide -- the recommendation of a professor that I met once at a conference likely isn't enough. We mostly contact personal friends and close collaborators here.
- Tier 3: students that applied because of a job announcement we put out. We generally only do that (putting out job announcements) if we really need a position filled and we could not find somebody in our network. In most cases, my lab head is more ready to leave a position unfilled than hire somebody that does not come with a strong recommendation.
- Tier 4: students that applied with a cold email. As far as I know, we have literally never hired somebody that applied cold.
Which of those "tiers" you fall in is the single most important factor that leads to whether you will be hired or not. In the rare case that we have multiple students that come with strong personal recommendations, and we cannot hire all, we usually select roughly following these criteria (roughly in order of importance):
- Research experience. A master is a prerequisite for PhD studies in my current country. However, most master students don't publish. If you did, it is certainly perceived very positively as long as the paper is at least ok. (publishing in predatory journals or other really bad venues might be perceived negatively actually)
- Relevant industrial experience. We do research on software engineering, so if you worked as a software engineer before, this will be perceived positively. However, note the "relevant" here. Standard internships or jobs may not help much (most have done those at some point) -- it needs to be something that we think will clearly give you better insight into our area of research.
- Technical skills. We don't expect future students to know how to do research yet, but we expect a strong programming background and fluency in standard tooling.
- Perceived compatibility with the team. Finally, we also typically consider whether a student is a good fit for our lab culture.
The last two bullets are typically assessed in interviews. We generally interview candidates via Skype beforehand, and (when we are almost certain we are going to hire a student), we also fly her/him in to give a talk in our group and spend some time with us beforehand. (both things we only do for Tier 2 - 4 candidates)
We don't ask for letters of recommendation (of people we do not know), research statements, statements of motivation, or anything like that. Neither do we look at previous grades (except maybe in a corner case, but to the best of my knowledge it has not happened yet).