You will generally need to start to get ready a full year before you plan to start your intern year. That's July or August. You then apply in September, interview in October-January, match in March and start in June.
When do you graduate? Are you a summer or winter graduate? That will decide your timeline. The timing of the boards is important, too.
Pre-matches are horrible things from the past that will hopefully be outlawed soon (my personal opinion). They still exist this year.
Very few, if any, programs will pay for your plane tickets. It involves a lot of flying if you're in Europe during the interview season (which I am) but that's life.