Another parent of an older child told me that when kids first start writing, it's important to just encourage them so they think writing is fun. So that, and the return messages, is all we've been doing.
I want to make sure to support this/encourage this in a developmentally appropriate way as needed. And I want to make sure I shouldn't been doing something more.
We don't do explicit teaching. We make sure notebooks and writing implements are available all over the house. We leave our kids notes, and ask them to be responsible for writing the good stuff (ice cream flavors) on the shopping list sometimes.
We want it just taken for granted that when you're waiting somewhere, writing notes (especially in code) is just a fun thing to do. If they say "I'm bored" they get a pad and pencil. They've noticed that all the other kids get electronics while waiting. Ah, well.
