По какому волшебству в Laravel работает Hash::check() — ведь хэши генерируемые Hash::make() всегда разные?
Если посмотрите на хэш, то его можно разделить на несколько частей
$2y$10$jSAr/RwmjhwioDlJErOk9OQEO7huLz9O6Iuf/udyGbHPiTNuB3Iuy2y - тип хэша, BCRYPT.
10 - алгоритмическая сложность bcrypt.
jSAr/RwmjhwioDlJErOk9 - 21 символ соли.
OQEO7huLz9O6Iuf/udyGbHPiTNuB3Iuy - собственно хэш.
При генерации хэша задаётся случайная соль, поэтому хэш каждый раз разный.
При проверке пароля параметры хэширования берутся из строки проверяемого хэша, поэтому при правильном пароле хэши совпадут.
1. У одной строки может быть несколько (кстати, а сколько их всего там для одной строки?) хэшей?
Это неверно. У одной строки может быть только один хэш (иначе бы эта функция не соответствовала бы определению хэш-функции). Верно наоборот - один и тот же хэш может быть результатом хэш-функции от разных строк, это называется коллизия. 

2. Каким чудесным Hash::check() узнает что разные хэши происходят из одной и той же строки?
Из неверного предположения в п. 1 идёт неверный вывод о чуде в п. 2.