Quando ti immergi nella documentazione di mysql e cerca la funzionalità RAND() vedrai che puoi usare un "seme".
Utilizzando un seme otterrai sempre gli stessi risultati randomizzati.
Esempio:
$products = Product
::all()
->orderBy(DB::raw('RAND(1234)'))
->paginate(4);
Puoi generare il tuo seme e archiviarlo in una sessione o qualcosa per ricordarlo.
Aggiorna
Il generatore di query Laravel ora ha una funzione che fa esattamente lo stesso:
$products = Product
::all()
->inRandomOrder('1234')
->paginate(4);