Just like with public schooling, the parents MUST be involved with their childrens' education and lives.
Shop around. We had originally planned on a Karate place near our home, but asked around, and decided on the less-convenient TKD place. We found that most of the places would give the kid a free lesson so he could try it out, and they all offered a short-term introductory schedule/price. FWIW, my wife is taking TKD with him, so it's become a family activity. Also, be prepared to shell out a few bucks. None of the places we looked at were cheap.