Additional stress should be laid on several elements in NetCurl's excellent writeup. My advice is limited to the system in the USA, which is the one I know; and my field is the humanities, not the soft or hard sciences. See the other caveats at the bottom.

Choosing a school.

Graduate schools are selling a product. A lot of people recommend looking at rankings, but the latter do not tell the whole story. As a prospective customer, get on the phone (or write an email) to the graduate advisor (or some similarly-titled equivalent) of the department in which you are interested and ask them a pointed question: have recent graduates of their program been hired, and (more importantly) where? Any good school will be glad of its bragging rights and its representatives will not resent the question (any resentment or unwillingness to answer should be read as a red flag).

If you are planning to enter an academic field (the only choice about which I am competent to give first-hand advice), be wary of any school that does not send its graduates on as assistant professors to schools in the top X of those rated in your favorite guide to graduate schools. "Assistant professor" is an important distinction: it is the default title for professors hired on the "tenure-track," which means the institution hired them with a view to keeping them. Visiting assistant professors and adjunct professors are in a different category--lots of people are hired right out of graduate school for one-year stints, and because the institution has little invested in the temporary hire, these positions tell you correspondingly little about the graduate school's clout, the student's quality, or the hiring institution's opinion of the student. (As a hiring institution, Harvard is an exception. They characteristically hire good people right out of graduate school for only a few years with no real chance of tenure. For tenured faculty, Harvard prefers to hire big guns who've already proven their mettle elsewhere.)

I wrote "top X" above because a mere number won't do. Maybe you prefer liberal arts colleges; maybe you want to buckle down and do research without bothering too much about interacting with students; maybe you want to take another route, and enter secondary-school teaching. You'll need to think hard about the names of schools at which a prospective graduate school places its graduates. But I dare say, this is the most important consideration of all. If a certain department does not place its graduates well, your chances of their placing you well, no matter how good you are, will be diminished (though by no means zeroed out). This is regrettable, but a fact of academic life.

Letters of recommendation.

Given grade inflation, letters of recommendation are arguably more important than grades. You should think very carefully about whom to choose, and you should expand your options by going in and getting to know your professors better. The payoff is that they will get to know you better, and a letter of recommendation chock-full of anecdotes and specific examples is extremely powerful. A teacher who's on the ball will ask to interview you before writing if he or she doesn't know you very well. Watch out if the teacher seems to take the whole thing as pro-forma. You might get a generic letter. It doesn't hurt to get your request in the queue early--profs tend to get swamped with them about winter final exam time, as students take care of business before going home, and your letter may suffer from being part of a large number written all at the same time.

Obviously, you want at least one professor from your chosen field of graduate study to write for you; but it does not hurt at all if one of the (usually) three is in an unrelated field (or from the "real world," for that matter). I am in the humanities and regularly write in support of medical school applications, and tracking results shows that this hasn't hurt them at all. Likewise, a humanities aspirant would be well served by a good letter from a math or science prof. NetCurl is right: ask the professor straightforwardly if they can write a good letter for you. Some profs will agree to write while avoiding the unpleasantness of telling you they don't think highly of your work, if you do not trouble to ask. This is all the more important because you should always sign the waiver relinquishing your right to inspect the letter later. Letters written by professors with the expectation (or fear) that the candidate will read it some day are far less powerful than ones the candidate has waived the right to see.

Resume.

Most graduate applications do not require one. Nevertheless, get one written and keep it up-to-date, so that you can give it to your recommenders as a summary of your achievements even if you don't need to send it in with your application.

Everyone has their pet peeves and strong preferences here. My recommendation is: create a CV (= resume) specific to what you want out of it. If you are applying to graduate school, there's little need for an "objectives" section. Likewise, put your information in the order a graduate school (or someone writing to a graduate school on your behalf) will want to see it in: academic information (schools, awards, publications, if any), then work experience. Don't clutter your CV with high school achievements or vaguely self-congratulatory personal stuff like your age, marital status, smoking status, etc., etc.

At all times in your career, format your CV for legibility. Admissions (and job search) committees have to look through hundreds of CVs, and a clearly arranged one (that avoids splashy graphic effects) will be more likely to impress them. Be honest. We academics are masters at padding our resumes and you play our game at your peril.

Personal statement.

Everyone is agreed that these are not very significant. So why are they required by a great many applications? It is a brief writing sample that has not been corrected by a professor, and may just represent something like your native writing and organizing skills. That means it's not there to get you thrown out of the pile if you don't find something terribly odd or clever to say about yourself--it's there to get you thrown out if you have not the wit to write a clear, syntactically-correct, properly-spelled essay in an application you theoretically care very much about. Any good professor will be willing to read your personal statement and suggest ways to make it better (though not perhaps at the moment you ask--think ahead). You may just impress someone with an offbeat essay, but that's not the purpose of the exercise.

Publication(s).

I am of two minds here. First of all, the publication rat-race ought really to start no sooner than you've found a job. Publishing takes a lot more time than just the research and generation of workable ideas, and I think that for a student, this time might best be used filling your head with the general knowledge necessary for your field. But the real world imposes a different view: more and more graduate students are publishing these days, and these publications are occasionally quite good. By a process analogous to grade inflation, it's now becoming more and more common for undergraduates to publish papers in venues designed to receive such work. So sooner or later, it may actually become a default necessity to publish as an undergraduate.

After being accepted.

This is the time to visit a school or two, if things have worked out such that you have a choice. Let them sell the school a little more; ask them again about recent hires among their graduates; ask to talk (with no professors around) to a couple of their graduate students. Is the culture at that school hellishly competitive? Do students there apply for and regularly win grants, or fellowships to study abroad? Are the graduate students happy? Are they left to fend for themselves? Do they seem to get along together? These will be your friends within a year: choose wisely.

Again, intelligent people of goodwill will differ, but if you are in the humanities and not independently wealthy, I advise against going to a school which does not offer you sufficient free or TA money to support yourself and a remission of all or nearly all student tuition and fees. The last thing you want is to graduate with massive student loans to (possibly, if everything works out right) about a $45,000/annum starting salary. Better to do some further undergraduate studying, GRE practice, or other remedial work if your resources will permit it and apply again the following year.

On cultivating professors.

There is a respectable school of thought which recommends getting to know a big professor in your area of interest at your undergraduate institution. The idea is that this prof will write a letter with clout, and that is a good thing. But be sure to get a letter from a younger faculty member who remembers what it's like to be applying and hasn't lost her or his fire. There is a notorious professor in my field who writes essentially form letters for every student--all of them worthless "this is the finest student ever" letters. Very embarrassing when two letters from the same prof cross a committee's desk!

Truth in advertising:

I went to graduate school in the late 80s and early 90s. Having done one-year stints for several years, I was hired as an assistant professor (in a liberal arts environment) in 2001; now, in a case of the lunatics truly running the asylum, I write letters of recommendation every year, and have vetted applications for fellowships and jobs. I have never sat on a graduate school admissions committee, however. Use my advice with an eye to my limitations, and, as with any advice, get a second opinion!