Как устроен VPS/VDS сервер?
Буква V значит "виртуальный". Поэтому это не голое железо, а голая виртуальная машина, периодически мигрирующая с одного реального сервера на другой в ЦОДе. В остальном всё верно, настраивать операционку, ставить на неё СУБД, web-сервер и прочее придётся самому. Windows можно использовать, но зачем вам платить хостеру не только за сервер, но и за лицензию?
Windows тоже используется.
Однако широко используется Linux и FreeBSD. Для основных задач в интернете - Linux/FreeBSD вполне подходит. Windows нужна крайне редко, в основном под терминальные сервера.
Сейчас уже никто не ставит все это ПО вручную.
Есть готовые системы управления виртуалками - они всю черновую работу сделают за вас.
А так, да.
1) Голое железо
2) На него ставится обычная ОС, поддерживающая виртуализацию гостевых ОС.
3) Ставится ПО, управляющая виртуализацией
4) Это ПО само, по приказу человека создает и включает гостевую ОС. Поскольку задача создания/убивания гостевой ОС типовая, то никто не делает это вручную. Поручают ПО.
5) Иногда используются более эффективные механизмы, которые жрут меньше ресурсов чем полноценная гостевая - типа Jails во FreeBSD.
6) ПО в гостевую ОС не обязательно ставится. Может просто "прокидываться" внутрь гостевой предустановленный комплект ПО. Может подключаться специализированный образ ОС, с предустановленным ПО.
Первым делом на него нужно установить ОС, а потом уже на эту ОС устанавливать сам сервер, БД, ЯП и т.п.? Или как?
Еще по поводу ОС. На сколько понял Linux server это единственный вариант? Наверное можно и Окна или еще что поставить, но я так понимаю что линукс все таки самый оптимальный вариант в плане "под сервер".? 
Установка языков и пр. - это вопрос того, кто управляет гостевой ОС.
Он может поставить все что захочет.
Все что ему надо.
Как правило достаточно установить 1-2 нужных тебе основных продукта - остальные подтянутся автоматически, по зависимостям.
Линукс не оптимален
Зависит от задач.
VDS/VPS ставит хостер.
Что вы паритесь?
Если вы хотите стать хостером, то VDS/VPS это одна из моделей разрезать железо и продавать различным пользователям и не иметь с этим гемора, так как все изолировано.
Есть куча ПО которое все это сделает и деньги даже вам посчитает.