Which view do I have to use to make the order of the images random in Node Gallery Slideshow?
Under admin/build/views/list, look for node_gallery_gallery_image_views. Your probably looking for the 'view all image thumbnails' display here to have it randomize a full gallery. The current display order is based on your node gallery image weight so you'll want to remove these under 'Sort Criteria' (click the up down arrow icon to remove these settings).

After that, you want to add a sort order criteria, 'Global: Random' to have the results of the view sorted randomly.

Note: this will apply to all of your galleries since it is accepting an argument of the parent gallery node object. If you want this just to apply to one specific node_gallery, you'll need to clone the display first and adjust this argument.