My minor child incurred income taxes on the sale of stocks that I gifted him.
If I pay his income tax with my own money in 2010, does it become a gift for the year 2010? (meaning that I need to reduce my tax-free gift amount by the amount of tax I paid for him)

Yes, it will be considered gift. You can give gift of up to $13.000 in a year. Your spouse can also gift up to $13,000 separately.
Yes, it the amount exceeds $13,000 then you must file the gift tax return and the excess amount will reduce your life time gift exclusion amount of 1 million.