Always make a backup before installing a new version. If anything goes wrong (could be a bug in the program, could be a mistake on your part), you want to be able to revert back to where you started fairly easily. The backup that I made of the gallery directory before my last upgrade was only about 1 MB. Compared to the potential pain of screwing up and having to start over from scratch, that's nothing.
1) Download new version
FTP the newest .tar.gz gallery install file (it's called a tarball) to the directory on your website that contains the gallery directory. For my site, that's the wombatnation.com directory.
2) Run configure.sh from ssh
Start an ssh session
cd into the gallery directory
Put Gallery into configuration mode
->[servername]$ sh configure.sh
3) Backup current version
cd up one directory level
->[servername]$ cd ..
Use tar to compress and archive your gallery directory
->[servername]$ tar -cz gallery > gallery-backup.tar.gz
4) Unarchive new version over the old version
->[servername]$ tar -xvzf gallery-1.x.x.tar.gz
The above command will overwrite old files with new files.
5) Go through the configuration wizard in a web browser
In a web browser, access the URL for your albums directory. Go through each page like when you did the original install.
6) Run secure.sh from ssh
In an ssh session, cd into the gallery directory
Put Gallery into secure mode
->[servername]$ sh secure.sh
7) Use the special upgrade_album.php URL to upgrade all the albums