The links may get broken, but that's not a terribly large issue.
Just use Explorer or Finder to move everything to the other location. If you ever need to reedit, move them back to their original locations.
Use the Project Manager within Premiere - ""Collect files and copy to new location". There is also an alternative which can reduce the size of the stored project if the files can be trimmed.
As Jim says, you will have to re-create the links to the media if you open the stored project.
Is recreating links a one button click?
I wouldn't be going back to the original locations.
It depends on the arrangement of your assets, but you will be asked to locate an item when you open the project and be presented with a window to navigate to locate it.
Make sure to check the box to make the required asset the only one that shows - this makes life much easier. The program will then locate as many assets as it can, but may ask you to locate another asset.
You can minimise the number of stages here if you do not re-organise the files after the Collect and Copy process.