There are a lot of options.
O - old site
N - new site
a) copy via FTP from O to your PC all image files with thumbnails and export your database from O, then copy your all images with thumbnails to your server N and import the database
b) copy only original images from O then copy then to N, install new Phoca Gallery and let Phoca Gallery create thumbnails from these files
c) Jan prefers: copy all images with all thumbnails from O to your PC, then copy these images into your server N, install new Phoca Gallery, run Multiple Add and Phoca Gallery will do new categories and subcategories from your folder structure. The goal of this solution is that Phoca Gallery need not make the thumbnails, it only checks to see if the thumbnails are ready so Phoca Gallery only writes data into database, which should be very quick.
d) Jonathan says: If you are creating a new Joomla install, on the same server (after a hack, for example!) I simply copied the whole images/phocagallery folder to the new Joomla install, using my ISP online FTP. Running Multiple Add in PhocaGallery sorted everything quickly. This is potentially dangerous if hackers have messed with your phocagallery, but I was fortunate!