Где искать клиентов?

Каким образом искать заказчиков в социальных сетях и связываться с ними?

Это отдельная наука SMM Читайте. Тут в два предложения не ответить. В сети куча учебных материалов.

Какие каналы принять во внимание?

Вы бы уточнили о каком ПО речь. Иначе могут ГорВодоКанал предложить и будут правы.

1. Возможно подать рекламу в тех местах, где тусуются ваши потенцильные клиенты - форумы, мероприятия, интернет-площадки
2. Организовать вебинар бесплатный (но как привлечь на него аудиторию, не знаю...)
3. Можно завести ютуб-канал, либо блог, с интересными статьями (сам себя пинаю - не получается начать даже :D )
4. Создать посадочную страницу и запустить директ (эдвордс)
5. Начать обзванивать потенциальных клиентов в других городах
6. Выйти на знакомых в других городах, использовать личные связи в других городах
7. Вести PR-деятельность (публикация на отраслевых площадках, размещение партнерских материалов за деньги)

Крейглист говорят ещё хорошо заходит