What year should you start internships for a Computer Science major?

Start looking right away (why not .. the money is usually pretty good for a first time job).

You may get lucky and snag an internship as a freshman.

As a college freshman, especially in Computer Science, Internships are extremely valuable, as they provide you with a paid, invaluable industry experience which can very likely translate to a full time opportunity. I found that without much experience, the most important steps are (like Tom mentioned), 1. Getting an interview, 2. Passing the interview. Although getting an interview as a freshman can sound quite daunting, I have found several ways that anyone (yes, even high schoolers) can get noticed.

1. 
   

   Have an active Github account and work on open source projects with others

   
   


2. 
   

   Participate in ACM, Code Jam, Bubble Cup, Code Chef or other programming competitions

   
   


3. 
   

   Try to attend local hackathons, they can be quite rewarding (allowing you a chance to learn about different technologies) and provide a great resume booster (I recommend Meetup: find your people)

   
   


4. 
   

   Establish your online presence with a blog or post your coding samples to demonstrate your technical abilities

   
   


5. 
   

   (The most important one) Make sure that programming is what you love. Having completed internships at Amazon and Google (Summer, Fall 2013), I can tell you that how much you get out of Software Engineering is exactly how much you put into it, so you might as well make sure it is something that you truly love!

   
   

As for career fairs, make sure you go to as many as possible and maintain a specific and relevant but yet concise resume to present to recruiters. Including your languages and technologies that you are familiar with on your resume is a MUST for software positions.

As for interviews, I strongly recommend the same book as Tom, Cracking the Coding Interview, by Gayle Laakman, as it has helped me on numerous occasions, along with practicing on websites like Programming Interview Questions | CareerCup, LeetCode and Project Euler. I find that simply walking through each problem in the book is not enough, so I frequently find myself on CareerCup seeking for more practice :) You don't have to complete every single question on those websites, but simply do a couple questions everyday. You would be surprised with the results! :)

First year is never too early. It just gives you a competitive edge and reveals your drive to start early and work ahead. You can start as early as mid-August. Some top companies fill up their internship positions by November or December so it is typically easier to look for an internship in the fall. February and March is around the time when there are no spots left for large to mid sized companies.

However, if you're late to looking for internships, startups sometimes accept interns just weeks before the summer starts.

Good luck!