One should strive to make a decision regarding fellowship training sooner rather than later. It is best for the decision to be basically finalized by the end of the PGY3 year for those in a 5-year program and by the end of the PGY4 year for those in 6-year programs. Having an early conversation with your chairman and/or program director regarding your goals is critical. The earlier your mentors probe their contacts and introduce your name to the right people the better.
Late summer/early fall of the year prior to graduation (i.e. PGY4 in a 5-year program and PGY5 in a 6-year program) contact the fellowship directors at each fellowship program where you wish to apply. Express interest in the fellowship and inquire into the logistics of the application process. Most program directors will reply within several days and tell you exactly what they want as part of your application. The typical requirements are 3 letters of rec and a CV. Some fellowships want a personal statement -- an insanely painful exercise for any self-respecting physician. The program directors will likely let you know at this point when to expect your interview. Be sure to keep track of the match registration deadlines for fellowships that select through a match process (e.g. peds, endourology). The good news: in general, this is not as competitive a process as applying to residency.