First and foremost: show up at the interview wearing only a grass skirt and coconut halves on your breasts. They seemed to love that and they're still talking about it...
Honestly, it is difficult to say and I think everyone has a bit different story. The many tips on this website that people give for getting into any medical school seem appropriate.
Obviously you'll first need the scores (GPA/MCAT) to get the phone interview (I've heard of non-URM getting a phone interview with a 3.5/30). Then impress them in the phone interview to get an on-site interview. Here are some tips for the interviews and personal statement.
Research both the Mayo tradition and the city of Rochester. I think they want people that understand the values on which the clinic and school were founded and people that follow those values in their personal lives. At the interviews be excited and positive about Mayo and Rochester. Mayo is extremely professional (e.g., the doctors at the clinic wear business suits, not scrubs or white coats) so be sure that you can relate to that and comment on what being a professional means. Know what it means to be a physician...the good and bad aspects. At my interviews I was never asked about any "big picture" topics (i.e., managed care, the un-insured, medical ethics, etc.). But rather, the questions and discussions seemed to focus on my personal background (i.e., life lessons that I've learned and how I've learned them), goals, and values and how they fit into medicine as a career.