I've gotten two internships at respectable software firms in my city.
An internship is invaluable for you snagging that first development position and it can also raise your initial salary a significant bit as well. Think about this: you are interviewing two candidates with similar skill sets straight out of college. One of them had a software development internship and can talk about real world projects he worked on. The other one can't. Who wins?
The Hunt
Many companies will often times advertise for interns on their website but I have never gotten an advertised internship. I always work hard at creating or finding opportunities that are not publicly announced.
The first software company I did a summer internship at, I contacted the HR department and asked who did technical recruiting. Don't waste your breath giving a huge schpeal to the wrong person. Get a phone number! This is important. Then, hang up and dial them yourself rather than be transferred so you know you can reach this person on your own easily.
Once I was on the phone with her, I told her that I was interested in doing an internship at her company. I didn't say, "Do you have internships available?". That is too easy of a question to say no to. I simply stated that I wanted one from her company and I wanted to know who to talk to on the development team about it. After some discussion I was able to get a team lead's phone number. Once I called him, I stated that I had previously talked with HR and I was interested in helping them out with some software projects over the summer.
He was interested! Honestly, if it sounds like you aren't going to need hour-by-hour hand holding I think most teams would welcome someone to take on a menacing project that others haven't wanted to do. After our conversation he said he would contact HR. This is important because now I have validity and his phone call back to HR holds serious weight.
The Kill
Now, I wait a day and call the technical recruiter HR person back (remember, we have her direct number!). I tell her that I talked with the team lead and that he said he was going to talk with her, but that I wanted to get the ball rolling on setting up an interview with both her and him in the near future. If you sound confident and make statements rather than a lot of weak yes/no questions you'll get a lot farther. She setup a date for the interview. Honestly, if you have an interview you are 95% of the way there.
Dress nicely at the interview. The formality of the business you are interviewing at will determine your dress but the minimum is dress pants and a button up shirt with tie. Even if everyone there is wearing flipflops and anime t-shirts. Come at least 30 minutes early. Play suduko in your car or something until a little closer to your interview time. It is better to blow a few minutes in your car before entering then it is to possibly get stuck in traffic and be late.
I've also been given a phone interview before a face-to-face. It was somewhat stressful being asked technical questions over the phone but nothing they asked was really that hard. Don't be afraid to say you don't know.
Don't wait around for companies to come to you for internships and don't wait around for them to post openings. Teams often are interested in having an intern but just haven't done the setup work to get one. Be skillful in getting past the HR person and talk to someone higher up on the development team. Make a detailed list of every major software company within a certain mile radius of your home and put them in order of your desire to work there. Start looking up phone numbers, making connections and making phone calls. It is a full-time, all day process.
Final Word
Last thing, be persistent. I've had companies say they will call back the next day and when they don't and it is 4:00pm I'll call them. One company said they didn't really have the budget for an intern at that second but I was so persistent that they were able to requisition the funds especially for me because I seemed eager to work there.
Good luck!