Правильно: Николай-угодник.

Начнем ответ все же со ссылки на словарную фиксацию: Джек-потрошитель. Теперь попробуем объяснить это написание. Существительное, присоединяемое к имени собственному и указывающее на какую-то характеристику носителя имени, является приложением и пишется через дефис, например: Иван-дурак, Иван-царевич, Марья-искусница, Соловей-разбойник, Человек-невидимка, Зевс-громовержец, Николай-угодник. Если характеристика, выраженная в приложении, воспринимается как прозвище (часть индивидуального имени), то написание меняется, ср.: Иван Воин, Николай Чудотворец. Возможность трактовать слово и как приложение, и как прозвище приводит в некоторых случаях к колебаниям в написании, ср.: Бова-королевич и Бова Королевич, Иван-царевич и Иван Царевич. Написание имени конкретного исторического лица, персонажа закрепляется в словарях, рекомендациям которых нужно следовать. 

Академические словари в своих рекомендациях не расходятся. «Русский орфографический словарь» под ред. В. В. Лопатина (М., 2012) и словарь «Прописная или строчная?» В. В. Лопатина, И. В. Нечаевой, Л. К. Чельцовой (М., 2011) фиксируют: Белый Бим Черное Ухо, Муха-цокотуха.

Первое написание соответствует правилу: «С прописной буквы пишутся нарицательные слова, выступающие как названия персонажей в сказках, пьесах, баснях и некоторых других произведениях художественной литературы, фольклора, напр.: Красная Шапочка, Змей Горыныч, Серый Волк, Синяя Борода, Дед Мороз, Петушок со Шпорами...»

По этому же правилу пишется имя персонажа в сказке К. И. Чуковского Муха. Но к нему добавляется приложение – имя нарицательное цокотуха 'тараторка, трещотка'. Ср.: Рокфеллер-старший, Дюма-сын; Илья-пророк, Николай-угодник; Иван-царевич, Иванушка-дурачок.

Главный ориентир в области правописания – академические орфографические словари и справочники. Рекомендации по написанию слов орфографического словаря на нашем портале соответствуют академическим.