How much available space per game in the Steam Cloud?

In your Steam library, you can right-click a title and select Properties. From here, select the Updates tab.

In the bottom part of the window, you can see exactly how much space is used for that game, and how much storage that game has left. Here's what it says on my computer for SpaceChem:

As you mentioned yourself, the permitted size does indeed vary per game; e.g. Portal 2 has 1 GB available.

This information is also available even if the title isn't currently installed.

Inside the Steam library, right click on a game and select "properties", then open the "updates" tab and you'll find both the total space available for that game and how much has been used.

Total space varies depending on title, for instance it's 100 MB for Half-Life 2 and 1024 MB for Team Fortress 2. Anyway, when you reach this limit your oldest saves will be automatically removed from the cloud (but not from your hard drive) to make space for new ones.