Learn Hardcore Icelandic: Ég set peysu og úlpu á mig þegar haustið byrjar. - I put on a sweater and a jacket when autumn begins.

So with ég (I), the correct present form is set, not setja.
The pattern “infinitive ends in -a, 1st person singular ends in a consonant” is very common in Icelandic verbs (e.g. tala → ég tala, læra → ég læri, setja → ég set).

Why do peysa and úlpa appear as peysu and úlpu here?

Peysa and úlpa are both feminine nouns. In this sentence they are:

singular
indefinite (not “the” sweater, just “a” sweater)
direct objects of the verb set

Direct objects in Icelandic are usually in the accusative case.

For these weak feminine nouns, the accusative singular ending is -u:

peysa (nom.) → peysu (acc.)
úlpa (nom.) → úlpu (acc.)

So Ég set peysu og úlpu á mig = “I put (on) sweater and coat (onto myself).”

Why is there no word meaning “a” in front of peysu and úlpu?

Icelandic does not have a regular indefinite article like English “a / an.”

peysa can mean “a sweater” or just “sweater” depending on context.
When you say Ég set peysu og úlpu á mig, it naturally means “I put on a sweater and a coat.”

If you want “the sweater / the coat,” Icelandic normally uses a suffix (a definite ending), not a separate word:

peysan – the sweater
úlpan – the coat

So for “I put on the sweater and the coat,” you’d say:

Ég set peysuna og úlpuna á mig.

What does the phrase set … á mig literally mean, and is it always used for putting on clothes?

Literally, set … á mig = “put … onto me.”

This is a very common pattern:

setja e-ð á e-n – to put something on someone

With clothes, this is understood as “put on (as clothing)”:

Ég set peysu á mig. – I put a sweater on (myself).
Hann setti húfu á sig. – He put a hat on.

It’s not limited to clothes, though. You can also:

setja krem á sig – put cream on oneself
setja plástur á sig – put a band-aid on oneself

So the structure is a general “put X onto Y” pattern; with clothing, it naturally means “put on (clothes).”

Why is it á mig and not á mér?

The preposition á can take either accusative or dative, with a meaning difference:

á + accusative → motion onto something (“to / onto”)
á + dative → location on something (“on, at” in a static sense)

The forms of ég are:

nominative: ég
accusative: mig
dative: mér

In this sentence the clothes are being moved onto you, so á takes the accusative:

á mig – onto me (motion)

Compare:

Ég set peysu á mig. – I put a sweater on (I move it onto myself).
Ég er í peysu / með peysu á mér. – I am in a sweater / with a sweater on me (state, no motion – here you would see á mér with dative).

Why does haustið have the ending -ið? Could I just say þegar haust byrjar?

Haust means “autumn, fall” and is a neuter noun.
The form haustið is the definite form: “the autumn.”

haust – autumn (indefinite)
haustið – the autumn

In Icelandic, when you talk about a season in a general, natural-cycle sense, you very often use the definite form:

Þegar haustið byrjar – when (the) autumn starts
Á vorin – in the spring(s)
Veturinn er kaldur. – The winter is cold.

Þegar haust byrjar sounds unusual or incomplete; native speakers would normally say haustið here.

What is byrjar, and how is it formed?

Byrjar is the 3rd person singular present tense of the verb byrja (“to begin, to start”).

Present tense of byrja:

ég byrja – I start
þú byrjar – you start
hann / hún / það byrjar – he / she / it starts
við byrjum – we start
þið byrjið – you (pl.) start
þeir / þær / þau byrja – they start

In þegar haustið byrjar, haustið (“the autumn”) is the subject, so you need 3rd person singular → byrjar.
Literally: “when the autumn starts.”

Can I change the word order to Þegar haustið byrjar, set ég peysu og úlpu á mig?

Yes, that is perfectly correct and very natural.

You have two clauses:

Ég set peysu og úlpu á mig – main clause
þegar haustið byrjar – subordinate “when”-clause

In Icelandic you can put the þegar-clause first:

Þegar haustið byrjar, set ég peysu og úlpu á mig.

The comma is normally written in Icelandic when the subordinate clause comes first.
The meaning stays the same; you’re just changing which part you emphasize or introduce first.

What’s the difference between þegar and hvenær for “when”?

Both can translate as “when,” but they’re used differently:

þegar is a conjunction meaning “when” in the sense of “at the time that…”, introducing a clause:
- Ég set peysu á mig þegar haustið byrjar.
  I put on a sweater when autumn starts.
- Þegar hann kom, fórum við. – When he came, we left.
hvenær is used mainly in questions (direct or indirect) meaning “at what time?”:
- Hvenær byrjar haustið? – When does autumn start?
- Ég veit ekki hvenær hann kemur. – I don’t know when he is coming.

So in your sentence, because it’s a “when X happens, Y happens” structure, þegar is the right choice, not hvenær.

How would the sentence change if I talk about someone else, like “He puts on a sweater and a coat when autumn starts”?

You need to change the subject pronoun, the verb forms, and the reflexive pronoun:

Hann – he
3rd person singular of setja is setur
“onto himself” = á sig (3rd person reflexive pronoun)

So:

Hann setur peysu og úlpu á sig þegar haustið byrjar.

Breakdown:

Hann – he
setur – puts (on)
peysu og úlpu – a sweater and a coat (accusative)
á sig – onto himself
þegar haustið byrjar – when autumn starts

Are there other common ways to say this idea in Icelandic, or is set … á mig the only one?

There are several natural options; they differ a bit in nuance:

Ég fer í peysu og úlpu þegar haustið byrjar.
Literally “I go into a sweater and a coat,” idiomatically “I put on a sweater and a coat.” Very common with clothes.
Ég klæði mig í peysu og úlpu þegar haustið byrjar.
“I dress myself in a sweater and a coat.” Slightly more formal/explicit.
Ég klæði mig þegar haustið byrjar; ég er alltaf í peysu og úlpu.
“I dress (more warmly) when autumn starts; I always wear a sweater and a coat.”
Your original:
- Ég set peysu og úlpu á mig þegar haustið byrjar.
  Quite literal, focusing on the physical act of putting the clothes onto your body.

All are grammatically fine; fer í and set … á mig are especially common for everyday speech about putting on clothes.