I got a notification that some games have updates. Do I need to download everything all over again?

Depends. If it is an update for the game, there is usually just a patch file to download or Galaxy will apply the update for you. However, GOG doesn't just update the games, they also release updates for the extras. When you get an update notice, you should check what exactly got updated before downloading anything.

Some updates do require a download of the full game, while others have just the smaller patch files. Varies by title, developer, etc.

When there's an update, go to that game in your library. Then click on "More" and then "Changelog". It'll tell you what got updated (at least most of the times). Another thing to note is that you don't need to download every file every time there's an update. For exemple, if you downloaded your game when you bought it, say:

Name of game 1.1.0 (gog 1) 2GB

If it gets upadated you might get either:

Name of game 2.1.0 (gog 2) 2.4GB
(which means they don't offer a patch and you need to install this file to get the updates)

OR you might see:

Name of game 2.1.0 (gog 2) 2GB
Patch 2.1.0 50MB
(meaning if you downloaded the 1.1.0 (gog 1) version, you only need to download the 50 MB patch that'll get you to 2.1.0)

It can also look like this:
Name of game 3.1.0 (gog 3) 2GB
Patch 2.1.0 1.1.0(gog 1)->2.1.0 (gog 2) 50MB
Patch 3.1.0 2.1.0(gog 2)->3.1.0 (gog 3) 50MB

In this instance if you have the base game already downloaded (1.1.0) you'd need to download the 2 patches to get to version 3.1.0. OR you could decide to download the "Name of game 3.1.0 (gog 3) 2GB " which is the the base game + 2 patches in one download.

The only thing I'm assuming is that if you skip a patch (and it's not available anymore in your game list) then you need to install the whole game again (i.e. just the file for "Name of game 3.1.0 (gog 3) 2GB "). If I'm wrong I hope someone will correct me.

Hope this helped a little.

As cogadh said, be sure to check what has been updated before downloading anything. Go to the game in question on your account (you can filter the list to only show games with updates). Click on the game, then in the window that opens, click More->Changelog. That will tell you what has been changed.

Quite often it's something like "Fixed spelling errors in the Russion localization of the Linux version", which, if you're playing the game in English on Windows, can safely be ignored. I only download updates that actually affect me.