Get-ChildItem -path d:\ -filter *.mp3 -recurse | foreach {$_.FullName} | sort {Get-Random}
や、
Get-ChildItem -path d:\ -filter *.mp3 -recurse | foreach {$_.FullName} | sort -prop @{Exp={[Guid]::NewGuid()}}

でうまくいきそうです。　ありがとうございました。