Pick a new song randomly each time a song ends. This is the naive way to do it and can result in playing the same song twice.
Randomly shuffle the list of songs once and then go through the shuffled list in order, guaranteeing that no single song gets played a second time before all songs have been played.
The strategies are different, but I’d argue that they’re equally “random.”
I’ve got a cheap Chinese aftermarket head unit in my car that uses strategy #1, and it’s mildly infuriating.