Josh and Crys are, of course, right, but that won't stop me from being my usual overly verbose self. If you are comfortable with using a command line shell, e.g., bash, then connect to your server via telnet or ssh. From there, you can even use ftp from the command line to open a connection and directly copy the tar.gz file to your server, assuming the other server allows ftp connections.
If you want to use a GUI for most of the work, though, you can always use a web browser to download the file to your local hard drive and open it in a utility like WinZip. Winzip, at least recent versions, understands the tar and gzip formats. I often go this route, because I find it easier to quickly examine the contents of the archive and browse through the documentation before uploading it to my site.
Of course, since you need to get the tar.gz file up to the Linux server anyway, you then need to turn around and use an FTP tool like WS-FTP or one of the tools for Mac OS X to upload the file. It will likely be quicker to upload the whole file and then unpack it on the server with the command Josh listed above.
If you want to install Gallery, you really should get familiar with ssh. It's hard enough to install Gallery as it is. It would be even worse using just FTP.
I wrote up some notes while I was installing Gallery on my site. Since I ran into some problems that took a couple iterations to solve, I can't guarantee these notes are an exact step-by-step road to success. I haven't had time to do another complete fresh install to verify them, so please take them with a grain of salt.