よろしくお願いします

Dissecting this phrase, the yoroshiku part literally means "well" (in the adverbial sense of "good"), and the onegai shimasu part means "please," or more literally "I pray thee." So you can think of it as a way of saying "Fare ye well" in Japanese. Here are the real uses of yoroshiku onegai shimasu, and its less-formal twin cousin dozo yoroshiku:

  1. When meeting someone for the first time. Say "Hajimemashite." Tell them who you are. At the end, throw in a Y.O.S., and you're done. Painless!
  2. When you introduce yourself to a group of people. "(your name here) to moshimasu. (insert other pertinent bs about yourself) Yoroshiku onegai shimasu."
  3. When being introduced. If you're at a meeting, and someone says "Kochira wa gaijin-san desu," you stand up, bow, and say "Yoroshiku onegai shimasu." This is to prove that you're paying attention, I think.
  4. When concluding a speech. You can also say arigato gozaimashita, "thank you very much." Or you can say both, if you really want to be a linguistic bad-arse.
  5. When thanking someone. Even if you already know them. A simple "yoroshiku" is often more authentic than an "arigato" when you're with friends.
  6. When congratulating someone. Again, even if you already know them. On New Year's Day, every person in Japan will be saying "Akemashite omedeto gozaimasu. Kotoshi mo yoroshiku onegai shimasu": roughly, "Congratulations on this new beginning—I pray thee well for this year, too." Same thing goes on weddings, childbirths, etc (although you'll need to use other stock phrases when opening, of course).
There are other uses for this phrase, but in general, it's what you say when you need to sound polite and don't know any other phrases that would work better. Along with Toire wa doko desu ka, "Where is the toilet?", this is probably the most useful Japanese phrase to master.