I may have found the answer. I didn't realize that it makes use of the Flash player data directory instead of somewhere more logical, like the Documents or Steam folder.
From the Machinarium forums:
Windows:
"%AppData%\Macromedia\Flash Player\#SharedObjects\{RANDOMWORD}\localhost\{PATH_TO_MACHINARIUM_INSTALL_DIRECTORY}\machinarium.exe\Machinarium.sol"
Mac:
"~/Library/Preferences/Macromedia/Flash Player/#SharedObjects/{RANDOMWORD}/localhost/{PATH_TO_MACHINARIUM_INSTALL_DIRECTORY}/machinarium.exe/Machinarium.sol"
Linux/Unix:
"~/.macromedia/Flash_Player/#SharedObjects/{RANDOMWORD}/localhost/{PATH_TO_MACHINARIUM_INSTALL_DIRECTORY}/machinarium.exe/Machinarium.sol"
Long story short...if you are regularly using something like Ccleaner to clear out your temp files, then your save games will get blown away.