Допустим, я написал программу с использованием сторонней библиотеки, и решил ее выложить, как сделать, чтобы...

Это зависит от пользовательской лицензии используемой библиотеки

На первый вопрос возможны два ответа - "допустим" и "не допустим". Выбирай сам, какой больше нравится.
А профессиональные разработчики постоянно пользуются сторонними библиотеками; строго говоря, без них особо ничего и не напишешь.

Открою страшную тайну 90% кода - чужие библиотеки (чаще конечно STL)

Детали зависят от используемой платформы и языка, но в целом, если у программы есть компоненты, от которых она зависит, то они ищутся в нескольких стандартных местах (в папке с программой в первую очередь). Соответственно вам нужно либо распространять свою программу архивом, с включением всех нужных библиотек, либо создать инсталлер, который будет размещать библиотеки в нужных местах. Кроме того, иногда требуется сопроводить вашу программу инсталлерами всяческих рантаймов или платформ, от которых она зависит. Либо указать зависимость от этих платформ в описании программы (например, можно приложить к программе инсталлер С++ рантайма нужной версии, или указать, что программа требует для работы установленную платформу .NET 4.5, в таком духе). Если вы используете одну из стандартных библиотек системы, нет нужды прикладывать её к программе (если гарантируется, что такая библиотека в системе есть всегда)

Вешай её в папку с прогой и пойдет везде.

Я проводил эксперимент и писал под дос без использования библиотек и это процесс не очень из приятных (ТАСМ: написал даже функцию IntToStr)... А на счет библиотек можно компилировать в lib(С++), dll(Windows),so(Linux) и class(JAVA) и тогда вы защищаете свой код от изменений (кроме реверса)

Библиотека должна быть в папке с программой или в другом месте, главное, чтобы программа могла получить доступ к ней.
Например ПРОФЕССИОНАЛЬНЫЕ РАЗРАБОТЧИКИ используют WinAPI и вообще стандартный набор функций. Зачем создавать свой костыль, когда уже все давно написали за тебя?