[Nathan]

"genki desu ka" is more of a normal greeting, not really an introduction sirs, as its just asking "how are you?"

お元気ですか？ (o'genki desu ka?)
How are you?

元気です、おかげさまで。 (genki desu, okage sama de)
I'm well, thank you.
Keep in mind this is the long formal version. A more common version excludes the "okagesamade" part.


Edit: SSJup81 has laid it out nicely.

始めまして　（はじめまして）　(hajimemashite)
Doesn't translate well literally. Think of it as a formal first hello.

*****
(name)です。　((name)です） ((name) desu).
I am (name).
*****
[Edit2: Removed "私は" from this sentence.]

[どうぞ]よろしくお願いします　（おねがいします）　([douzo] yoroshiku　onegaishimasu)
It's nice to meet you.

Words in the "[]" are not really necessary, and add levels of formality.