In general I think you want to wait as long as possible with the physics so you have a chance to take as many of the physics classes as you can. If you are finishing quantum fall of '08, I'd take the test that November/December right before application are due. Don't worry, most people will be in your same boat. I think the time it would take to self-learn enough QM for taking the GRE before then would be better spent doing more research. Just my opinion, of course. For the general, I'd sign up now for the next one available and get that sucker out of the way. Foreign language... whaaat? I've never seen or heard that requirement and I've done a lot of looking.
As for picking which grad schools to apply to, some people on here have suggested taking one of the practice tests available online (like the one on the official GRE website) to get a ballpark score, and they said to assume you could raise your score by 100 or so by studying. I think that's a pretty good idea.
I also think you probably have at least some vague idea as to where abouts you might score, and I would take that as a starting point and begin looking into schools. If you want to stay within a certain area, start with a list of all the schools that match that criteria. Start crossing the ones off you know you don't want to go to, and when you have a small enough list start visiting webpages and reading about research. Keep a list of the ones that look good to you. Include schools that might be ambitious, include schools that could be your super-duper backup. Take your list to your profs and ask them their opinions. Consider looking into a few programs farther away. Grad school is a great opportunity to experience something new for a few years, after which we can all run home if we want (I know I will!), but at least we'll have the experience under out belts for the rest of our lives.
If you're not sure what you want to research, Maryland might be good to look at because their department is so big. They have tons of neat stuff going on. A lot of schools require a lab-rotation "class" your first semester where you, well, rotate to a new research group every few weeks or so. That might be just the thing for you.