First of all, in order for the View to "remember" your random order, you will need to cache it. But that will show the same View to every user. The simple solution is to set a relatively short cache time, so that you get a new random order, say every ten minutes.
However, since you would like to take it a step further, you can do the caching "per user context". This will be quite complicated, but I will do my best to explain how you can do this.
I will suggest you use Panels and Page manager, to accomplish this. Both modules are fairly complex tools, that require some understanding to make work properly.
I will provide an outline below, and then I suggest these videos, for further information.
I make the assumption here that you have a dedicated "listing page". The solution should be applicate in order situations as well, such as the list being shown on a node-view, but will be slightly different.
- Install the Chaos tool suite (ctools) module, and Panels, and enable "Page manager", "Views content panes", as well as "Panels".
- Go into your View, and add a display of type "Content pane", leave it un-cached.
- Go to admin/structure/pages, and enable create a "custom page".
- Create a variant of type "Panel", pick any layout for now.
- Add your your content pane to the panel page.
- Go to Contexts", in the left menu. Add a "User" context, selecting "Logged in user".
- Go back to "Content", and in the top right of your view pane, click the little cog, go down to "Caching", and select "Change".
- Pick "Simple cache", any timeframe you want, and a granularity of "Context".
Now, you will get one individual View cache, per logged in user. If you want to make this work for anonymous users, things will become further complicated, since it's not obvious "who is who", so to speak. We first need to agree on what constitutes "a user". A simple answer would be "an ip-adress". Then we need to explain this concept to Ctools, but implementing a new Ctools context. Doing so is well beyond the scope of this question, but there is an example in /ctools/ctools_plugin_example/plugins/contexts/simplecontext.inc.