When I was a sophomore in college, I knew I wanted to get into a startup as an intern. (I think there is a pg essay somewhere giving that advice, I followed it). I knew as a mechanical engineer with some software development experience I didn't want to be in one of the web 2.0 startups. I posted an Ask HN question about how to find startups in Manhattan (I lived in New Jersey, about 1.5 hour commute to manhattan each way). HNers posted two groups (NYTech Meetup, and TechNY?, forget the second one off teh top of my head). I sent an email out to those two groups basically saying, here is my resume, I would love to intern for a startup company, preferably one that does hardware, does anyone have any tips.
One of the members on the 2nd board told me about Bug Labs, and gave me the contact email for one of the guys there. I then went through about a 4 week process of playing phone and email tag. I never gave up. I'd get in touch about every 3-5 days and push for an interview. I finally got one, I think just so they'd shut me up. They really had no need/use/idea of what to do with an intern. But I think they knew I wanted it badly enough that it was worth taking a chance on me.
I ended up staying there for the rest of college doing 2 summer and 2 winter internships, and it was definitely the best experience/job I've ever had.
My suggestion is: figure out exactly what you want to do, find a contact in the company (for me it was HR not CEO) and just lay it out really clearly why you want to work for them and what you will do. For me I made it clear that I would pick up all the low priority tasks and free up the other engineers to do other things. That meant at first writing a lot of the manuals, testing, and writing tutorials. It was probably less programming than some other internships, but I was surrounded by some of the smartest people I've ever met, and it was a great place to work.
So just don't give up on contacting them, people in startups are busy, and make sure you make it clear what value you are going to bring to them becuase startups don't have the time or money to keep on interns that don't pull their weight.