Фамилия Кокшенов — редкий случай, когда географическая основа почти наверняка перевешивает лично-именную. В её центре лежит название реки Кокшеньга (или Кокша) на севере Русского Заволочья, в современной Архангельской и Вологодской областях. Жителей по этой реке называли кокшарами, а выходца оттуда — Кокшеной (человек с Кокшеньги). Суффикс -ов в фамилии стандартно указывает на принадлежность: «сын Кокшены».

Менее вероятная, но допустимая версия выводит основу из диалектного «кокша» — так в северных говорах называли человека с непослушными, торчащими в стороны волосами или кудрявого. Но против этого говорит редкость прозвища в письменных источниках — в отличие от устойчивого топонима. Есть и третья гипотеза: связь с древнерусским именем Кокша, которое фиксируется в берестяных грамотах XII века, но это имя само могло быть образовано от того же речного названия.

Фамилия бытует почти исключительно на Русском Севере и в Сибири — в районах, куда уходили переселенцы из Архангельской и Вологодской губерний. Встречается она редко, что характерно для фамилий, привязанных к конкретной местности, а не к широко распространённому прозвищу. По происхождению Кокшеновы — скорее всего, потомки крестьян или посадских людей из бассейна Кокшеньги, а не дворяне: в родословных книгах эта фамилия не отмечена.

Словообразовательная модель здесь прозрачна: основа Кокшен- (от названия реки или прозвища жителя) плюс патронимический суффикс -ов. Ударение в фамилии обычно падает на второй слог: Кокше́нов.