Other Natural Methods
In addition to these ink formulas, there are others that you can play around with as well, although the results may not be exactly what you are after. It can, however, make for a really useful science experiment.
Henna is traditionally used in hair dyes, and as a decoration on Indian brides (much like tattoos). To get good results on paper you need to get hold of the proper dark henna (Henna Caravan does mail order), or the really traditional mehndi which gives more of a black color than the red/brown produced by henna. All you need to do here is to follow the packet instructions (these depend on the strength of the substance).
If you make it into a paste, you are better using a piping bag method to write or draw your design -- make one easily with a circle of wax paper, folding it into quarters, snipping a small piece off the pointed end and then opening it up from the top to put in your die.
Alternatively mix it to more of a runny texture and then use a brush to paint with it (see picture - painted onto rice paper).
Other natural ingredients you might like to try for making your own ink include tea and coffee -- combine it with either vinegar or a teaspoon of gum arabic to make it fix.