Как объяснить постановку запятой в предложениях типа: "Казалось, тихий ночной час придавал беседе особую прелесть" и "Действительно, камни бывают различной твердости"? Что это за часть речи?

В обоих примерах запятая ставится потому, что первое слово — вводное (выражает отношение говорящего к сообщаемому) и, как вводное, не является членом предложения, поэтому обособляется.

1. «Казалось, тихий ночной час придавал беседе особую прелесть.»
   Здесь казалось — вводное слово со значением предположительности («по-видимому», «как будто»). Его можно убрать или заменить синонимичным вводным: По-видимому, тихий ночной час… Смысл высказывания при этом не рушится → признак вводности.
   Важно отличать от случая, когда казалось — сказуемое без вводности: Казалось, что тихий ночной час придавал… — это уже сложноподчинённое предложение, «казалось» — сказуемое без обособления, а запятая ставится перед союзом что.

2. «Действительно, камни бывают различной твёрдости.»
   Действительно — вводное слово, подтверждающее истину сообщения («в самом деле»), поэтому выделяется запятой.
   Не обособляется, когда это наречие меры/степени внутри сказуемого/сочетания: Это действительно важно; действительно тяжёлый случай — здесь слово тесно связано со сказуемым и вводным не является.

Что это за часть речи?
С точки зрения синтаксиса — вводные слова. Морфологически они могут быть формами разных частей речи (в ваших примерах: казалось — глагольная форма, действительно — наречие), но в роли вводных они не являются членами предложения и потому обособляются запятой.

Быстрые проверки вводности:

• можно убрать без потери грамматической связности (Камни бывают различной твёрдости);

• можно переставить/вставить синоним (В самом деле, …; По-видимому, …);

• интонационная пауза после слова.