How can I add a carbonated water tap in my kitchen?
You need 3 major factors for this:

1) a source of CO2. Many people use paintball tanks which can be refilled. They come in 12 and 20 oz tanks so they would easily fit under your counter. But I bought a 20 pound tank as that seemed like the sweet spot for tank cost vs gas cost for me.

2) a tank to hold the pressurized water. For example, a 3 Gallon Pepsi style Cornelius keg is 17" high by 8.5" wide.

3) a way to keep the water tank cold. This is the hard part and I don't know of any easy solutions. I bought a 7 CF freezer and hacked the thermostat. It doesn't fit under the counter but my wife is ok with it because she drinks a LOT of carbonated water.

--
In response to the question about refilling the water tank:

The cheapest Cornelius kegs are used and hold 5 gallons/19 liters. That would last most people at least a week. So I just refill the keg as it gets empty.

I thought about other methods to refill the keg, partially with the aim of reducing the CO2 wasted when the keg is opened for manual refilling.

One idea is to buy a 2nd keg and use an air compressor to force water from the 2nd keg to the 1st keg. You would stop before the 2nd keg is empty so that air doesn't get into the 1st keg. Then you add CO2 to the 1st keg to bring it up to the desired carbonation level.

How much could you save by doing this?
Typically there is 2 to 4 volumes of CO2 in carbonated water. Let's assume we use 3. In other words, 20 liters of water would use 60 liters of gas. Also that we use 1 bar or 15 psi to push the water out. That's an additional liter of gas per liter of water. At one liter of water consumed per day, that's 365 liters per year of gas wasted by opening the keg to refill.

There are 229 liters of gas per pound and I paid about $1 per pound, thus the wasted 365 liters of gas costs $1.60. I don't think this is worth any effort to avoid at my price for gas. If gas costs you more, you'll have to analyze the tradeoffs for yourself.

Note that 20 pounds gives 4,580 liters of gas while 1 liter of water per day is 1,460 liters of gas per year. This means 20 pounds of gas will last over 3 years.

If you wanted something really automated, you could use a weight sensor to detect when the water tank was running low and turn on a valve to let more water into the keg. This assumes household water pressure is higher than keg pressure. For me, water pressure at the street is 100 PSI and my regulator takes it down to 60, much more than the 15 PSI that the keg uses.
If this is not your situation, you'd need a water pump.
The weight sensor also needs to signal when the keg has enough water and turn off the valve.

You'd also need a pressure sensor to detect when the keg pressure is too low and inject more CO2. I consider this too complicated for home use.

Another reason I do it this way is that my wife and I love the taste of San Pellegrino. I read an article describing how to make it at home.

http://blog.khymos.org/2012/01/04/mineral-waters-a-la-carte/

I was able to find a local brewery supply house that sold "Burton water salts". Mixed into the water at an appropriate ratio (I use 1 gram per liter), it tastes very good.

Since I have to mix the minerals into my water anyway, refilling the keg and pressurizing it as a batch process is no extra burden.

Here are some photos, I hope a link to facebook doesn't break any rules.

https://www.facebook.com/media/set/?set=a.10151813156323324.1073741838.770693323&amp;type=1&amp;l=eaa13eed3b