GOG / Steam / Humble Bundle are the main places where you will probably acquire your games. Among all services, prices tend to be elastic over time, and there are numerous sales during the year where you can buy games for half (or even less) of their full price. There are however differences between each service.
Steam is the distribution platform of Valve Software. It was originally designed to distribute Half Life 2 when it came out in a digital download format, and evolved since then as a full fledged distribution platform for many other companies and indie developers. Valve has also pushed for Linux’s adoption as a gaming platform by releasing a Linux Steam client in 2013 and porting most of their AAA games for it. It now has more than 700 titles for Linux from a number of different publishers or indie devs. While you can buy games on the Steam website (or via their mobile application), you need to get the Steam client to actually get the executable and data files on your computer. The client only runs on x86 architecture, and is currently only available for Windows PCs, OSX and Linux x86 PCs. Games distributed through Steam are mostly protected by DRM, but the practice depends on the publisher/developer. Some non-DRM titles are also available through Steam, but it is not clear when you buy a game whether the Steam client is mandatory to run the game or not. You can use the same Steam account on different home machines, so while DRM apply there are no huge restrictions on private use and Steam is rather practical and user-friendly. When purchasing games for Linux, you have to make sure there is a little Tux (penguin) icon in the platform list, otherwise the game may not be available for Linux at this stage. One Steam key gives you access to all versions of the game, so you could play the very same game on a Windows PC and a Linux one without having to purchase it again. Some games support the Steam Cloud feature which makes it possible to save your game state in the cloud so that you can pick up where you left from any other machine where you run the game from, as long as you are logged in with the same account.
Good Old Games (GOG)
Good old Games is the distribution platform of CDProjekt (based on Poland). It is specialized in older games (while they do offer newer ones as well, most of the catalog is currently based on older DOS or Windows games).
The key other difference with Steam is that all games are DRM-free and you get access to a complete offline installer for each title, making it possible to do backups of downloaded games. They have been offering Linux versions of some of their games since July 2014, and slowly expanding their catalog, reaching more than 100 in October 2014. While there is no client like Steam to download games, GOG is developing GOG Galaxy which will make it easy to buy, download and update games within a GUI client.
The Humble Bundle is a Y-combinator funded startup based in California. While they used to sell and distribute DRM-free versions of their games for all platforms (Windows, OSX and Linux), their business model is now mainly centered around reselling Steam keys without DRM-free download. The originality or their service is that you can usually buy a pack of games at reduced price, and often at the price that you want (while thresholds apply). They have added a full fledged store in their offering, called the Humble Store, where you can buy games for all platforms any time. DRM-free icons indicate you can download the actual installer, while a Steam icon shows that you get a Steam key instead.
On top of the three main distributors I mentioned, there are many other smaller shops you can find about everywhere, usually selling Steam Keys at lower prices. One good way to find them is to use comparison tools (do a Google Search for “Steam Keys +nameofyourgame”). Even if the Steam keys only mention Windows, if the game is available for Linux in Steam you will get the game for Linux as well. Note that some key activations for specific geographies (such as Russia) may need a VPN if you purchase them from a different country.
A Word of Caution
Note that not all games sold for Linux run “natively” on the platform. “Native” refers to code directly implementing the Linux graphics API, i.e. OpenGL/SDL. Many of older games sold by GOG run through Dosbox, a Microsoft DOS emulator. Some other games (such as Flatout 1 and 2), are wrapped with WINE to run on Linux – the Windows API calls are re-interpreted in OpenGL in real time, resulting in some loss of performance vs an optimized native version. The Witcher 2 is using another wrapper from eON, known as “Virtual programming”, probably implementing something very similar to WINE.
There’s always some ongoing debate in the Linux Gaming community about whether all games should run natively or if WINE wrapping is acceptable. There are some political positions at play here, but I think a pragmatic approach is also acceptable. If the resulting wrapped game runs very well on most configurations, then I’d say it’s a decent solution and a potential good way to do a cost-effective port. The Witcher 2 was originally heavily criticized because it was not running natively AND had a crappy performance at launch (on Linux). Since then, the company in charge or the port, eON, has massively improved its wrapper performance and the game now runs decently enough, while there is certainly a gap versus the Windows version on the very same hardware.
FOSS (Free or Open Source Software) Games
Linux being a Free OS (Free as in Freedom), there are many Free (aka Open Source) games available for the platform, some of them even of very high quality. While they rarely match what you can expect from a commercial game, they can nevertheless be complex and fun even if they are lacking in the art department (which is not always the case).