It seems that most states have no licensing requirement for polygraph operators. Considering that polygraphic lie detection lacks any scientific basis, I think it's appropriate that there should be no licensing requirement to practice it, just as one shouldn't need state certification to offer tarot card readings.

You'll find a list of states that do have licensing requirements for polygraphers, along with contact information for their licensing boards, on the American Polygraph Association website. (I don't know whether this list is comprehensive):

http://www.polygraph.org/statelicensing.htm

You are correct, and I was mistaken. It appears that more than 50% of the states (at least 28, as you correctly counted) do indeed have a polygraph licensing requirement.