Learn Russian: Я посылаю ему письмо.

ему is the Dative case form of он (he). We use the Dative case for the person receiving something. Since you are sending the letter to him, he is the receiver, so we must use ему. You would only use его (the Accusative case) if a person was the actual physical object being put in the mail!

Is письмо in the Accusative case here since it is the object being sent?

Yes! письмо (letter) is the direct object of the verb, so it is in the Accusative case. It doesn't change its spelling because neuter nouns ending in -о look exactly the same in the Accusative case as they do in the Nominative (dictionary) case.

Could I change the word order to Я посылаю письмо ему?

Yes, you can. Russian word order is very flexible. However, Я посылаю ему письмо is the most standard, neutral order (Subject - Verb - Receiver - Object). Moving ему to the very end would place special emphasis on it, meaning 'I am sending a letter to him (and not to someone else).'

How do you form the verb посылаю?

It comes from the infinitive посылать (to send). This is a standard First Conjugation verb. To match the subject Я (I), you remove the -ть ending and add the first-person singular ending -ю.