Learn Russian: Мне очень холодно.

In Russian, physical states and feelings are often expressed using "impersonal" sentences. Instead of saying "I am cold" with the subject Я (I), Russian expresses that the coldness is happening to you. Because of this, you use the Dative case Мне (to me). It literally translates to "To me, it is very cold."

Why is the word for cold холодно instead of the adjective холодный?

Because there is no subject noun (like "water" or "wind") to describe! In these impersonal sentences, you must use the adverb form, which ends in -о. You would only use the adjective холодный if you were describing a specific noun, like холодный чай (cold tea).

Where is the verb in this sentence?

Just like in basic sentences (such as "I am a student"), Russian skips the "to be" verb in the present tense. If you wanted to talk about the past ("I was very cold"), you would add the neuter past-tense verb было: Мне было очень холодно.

If I want to say "She is very cold," do I just change the first word?

Exactly! The state (очень холодно) stays exactly the same, you just change the person to the Dative case. "To her" is ей, so "She is very cold" becomes Ей очень холодно.