Both alcohol and water based will work but water based will raise the grain of the wood so you will have to sand them after applying it. With alcohol the alcohol will evaporate without raising the grain and may even penetrate the wood better.
Unsweetened Kool-Aid or RIT dye work well for inexpensive color with either water or alcohol.