tl;dr - Your best way to approach a company is to hand them a great resume. Optionally, ask a few questions that show you've done your homework and are genuinely interested in the problems the company faces, rather than just the job opportunity.

I'm not a recruiter, but I attend a couple of career fairs a year as a representative from engineering. I can tell you my own preferences, which may differ from those of other people you may find at career fairs. My advice is also likely applicable only to software engineering.

Your goal in coming to a booth at a career fair is presumably to get invited to interview. Since most desirable companies get far more applicants than they can possibly interview, you'll want to stand out.

Standing out has very little to do with what you do at the career fair. Your instinct is correct---starting with a speech is probably not the best idea. The most important factor is your resume. Did you build and ship some cool stuff? Put it on your resume. Haven't shipped anything? Put whatever you can (courses, class projects, etc.) on your resume---and start building and shipping.

When I read resumes, I'm seeking two signals: that you are good at writing software and that you actually like writing software. If you're red on TopCoder, had internships at companies like Microsoft, Facebook, Palantir, Dropbox, Google, and other places that take software seriously, or have shipped something of your own with significant uptake (e.g., if it's a mobile app, it has a lot of downloads and a high star rating), those are great signals. If you've taken a lot of hard, programming-intensive CS classes, or written software at a company not known for being serious about engineering, those are good-to-OK signals. If you've done something other than writing software, that's sometimes a good signal (e.g., if you were a Putnam fellow, I'm definitely going to read your resume very carefully), but more often neutral (if you were a summer intern in equity research, that's great, but doesn't tell me much about your programming skills.)

Some resume pitfalls that I often see:

• Passive constructions. If you didn't make a major contribution to a project, you might start a sentence with "Participated in...", "Helped...", "Assisted with..." or another passive construction. If you really didn't have a serious role, I guess you could do this, but you might as well just say exactly what you did or leave the item out entirely. On the other hand, if you actually drove the development of a project, say so! I've seen a number of resumes with passive constructions where the candidate really did lead the project. Start the sentence with "Wrote...", or "Shipped..." or "Designed..." or whatever, as appropriate.
  
• Vagueness. Avoid content-free "skills" sections. If you write that you're "Skilled at breaking down projects into tasks and executing on them", I've learned nothing. If you explain that you led a team of three fellow students to build a mobile inventory-tracking app for the campus library for a class project, I've learned a bunch.
• Too many pages. For fairness, I'll spend about the same amount of time on each resume---about as long as it takes to read a page. If it's seven pages of closely spaced text explaining that your last project used Rational ClearCase and JIRA, I'm probably going to miss the important stuff. One page should be enough for a new grad. For an experienced hire, two pages should be the absolute maximum. PROTIP: print double-sided or at least staple pages together. Two loose pages will easily get lost.
• Burying the lead. Your resume should ideally be ordered in the inverted-pyramid style of a traditional newspaper article. Put the most important section (usually education, if you're in school) on top. Put the second-most (usually work or projects, depending) below that.
• Overstated expertise. This will burn you in the interview rather than in the resume review. Avoid claiming you're an expert in something unless you really are.

If your resume is all-important, why go to a career fair at all? Why not just submit it online? (You should do this even if you go to the career fair, by the way.) Why do I go to career fairs? I go, and you should, too because career fairs enable two crucial activities.

Humanizing the company. Ideally, candidates will learn about what it's like to work at Facebook from their friends who worked there. But if they don't have friends who were interns, they might also have an impression cobbled together from press coverage, The Social Network, The Facebook Effect, and a number of less-than-entirely accurate treatments of the company in print. An enthusiastic engineer can convey the joy of working at the company. He or she cared enough to take time from his or her normal work to come to share that opportunity with candidates.

Reaching out to candidates with special skills or interests. It's hardly a secret that Valley companies are vacuuming up every mobile engineer that isn't bolted to the floor; if you have a lot of mobile experience, consumer-tech companies will be very interested. If you're interested in a specialized area that you know a company practices, mentioning this couldn't possibly hurt. If you're a good candidate, it could help a lot I was at a career fair last week where a candidate said she was really interested in a highly-specialized area of Facebook infrastructure---privacy engineering. I put her in touch with one of the lead engineers in that area. Conveying interest in the engineering challenges rather than the job itself (salary, perks, etc) is a great signal. PROTIP: Please be genuine about this; it's a waste of everyone's time if you couldn't care less about deep learning or privacy engineering or what-have-you but say so just to get in the door. It's fine to just hand over a resume without doing this.

So, what should you do at a career fair?

1. Build experience. The great thing about writing software is that you don't need anyone's permission. You can submit an app to the Android app store for less than what many people spend on coffee in a week.
2. Write a clear and succinct resume. You might want to tailor this differently for different sectors, but if you're an undergrad, you probably won't need to. Your school might even offer resume-writing workshops. Consider going, but remember that their advice might be tailored for non-technology companies.
3. Do some research beforehand, especially for consumer tech companies, and come prepared to chat about the product for a bit. If someone asks you about your favorite feature, it's much better to have one than to say "oh, everything!" or "nothing in particular." Part of the recruiter and engineers' job is to sell you on the opportunity and on why you should be interested, but they have to start somewhere. If you aren't interested in the product, why would you want to work there?

Best of luck.