Being into the decorating of eggs recently, an Orthodox tradition, and I am wondering which paints are most suited towards this type of work. My curiosity extends towards the possibility of using different dyes along with the paints.
Food coloring would be the easiest, most colorful and most common way of coloring eggs.
Alternately and perhaps more traditionally there are a number of natural dyes that come from food stuffs: purple cabbage, red onions, yellow onions, beets, teas. Typically these are chopped and boiled in water with a little clear vinegar in it until the color goes into solution. Then it works like any other coloring... dip, brush, or soak the eggs in it to give them color.
Food coloring is ideal for safe consumption, and when dying eggs, it's important to note that both the concentration of dye used and the length of time you leave the egg in the dye will affect saturation. An excellent addition to food coloring is to use beeswax to create white areas by resisting the dye. This is an excellent way to add contrast to your designs and a better alternative to painting white over the top of a dyed egg, as white paints often take many layers to fully cover a darker color. The beeswax is applied with a small tool, allowing for detailed designs like the ones pictured below.
A more kid-friendly option for creating wax-resist designs (and for adding color!) is to use crayons to draw designs onto the egg before dipping or submerging in dye. This will never look as tidy as the other method however.
Other safe options include edible metallic paints or glitter (often used in cake decoration) or even melting crayons with a hair dryer to create a dripping effect on the shell.