Untreated pine is generally the best wood to use for making your own toys. Cheap, safe and good for almost any size bird depending on how you cut it. Get the cheapest grade, your birds won't care if it is a little warped or has knots - in fact, they might add some extra chewing interest.
What my GCC likes (but she is a lighter chewer than a caique) is pine sliced into 1/4" slices across the grain. Cutting thin slices across the grain makes it very easy to chew. So you would take a piece of 2x2 or 2x4, drill a hole through it, and then just slice it off into 1/4" slices (or maybe thicker depending on how much your birds chew).
Bird-safe tree branches can also be cut into slices that birds love to chew - but be careful! If you are slicing them on a band saw be aware the branch will want to roll into the blade as you start cutting so be sure to hold the branch very securely and keep fingers away from the blade.
I don't dye wood myself. The birds don't care, and I use some colored beads between the wood slices to add interest. I've heard that the dye sold for cake decorating works very well.