Although Aaronut is entirely right in stating that you would be better off using alternate colourings that do not damage the texture of your icing, you can use normal food colourings, I do quite often.
When I use them on fondant or marzipan, the main issue is the capacity of the icing to absorb the colouring. They have limited ability to tolerate the liquid, so if you need a deep colour, expect a bit of a fight.
The best method I have come up with, is to treat it like pulling candy. Put the required amount of icing in a bowl and make a well and enough material to fold over that well. Put in a small amount of colouring and fold over. I tend to start off by squidging it about in folding motions to get the liquid in to the material, it'll be quite tacky at first. Then I roll it between my hands in to a sausage, fold in half lengthways, roll, fold, roll, fold...
It'll marble up to start with, given the folds, but eventually become one solid colour and will become less tacky with each fold, in a similar way that kneading bread makes it progressively more coherent.
Once settled, roll towards a ball/block rather than a sausage, then you can roll it out ready for use. If you are a very minute amount over the moisture level that you can roll it, try to incorporate a small amount of icing sugar (confectioner's) whilst folding to dry it out, like adding flour to bread.
It works, but is messy, take all rings off and expect to need to wash your hands a lot.
Edit
Found a video that roughly shows how I would do it, except the demonstrator has a different way of applying the colouring to the fondant initially and is using a much larger quantity than I tend to, so does not hand roll in the air as much as I would or as fast.
http://www.ehow.com/video_2333485_coloring-cake-fondant.html