What type of color should I use to color my shoes?
Shoe dye exists, in versions for leather and suede.  They should work reasonably well on natural fibres but the effect on synthetic fibres is less reliable (try applying, leaving to dry, then rinsing well).  Any plastic (e.g. vinyl) bits won't take dye.

Overall it's crucial to know what your shoes are made of before you start.