Since this comes up so often when testing games for developers and surprisingly often for newly released Linux games, I thought it might help to give developers a quick hint.
You've deployed your shiny new game onto Steam, later you've added a Linux version and it works fine for you. However, users are reporting a "Missing Executable" error that might look something like this:
It's usually very simple, it's a case of the Linux version not being correctly setup on Steam and it's something only the developer can fix.
A super easy way to check, is to look at the game on the handy SteamDB website, comparing the Linux and Windows lists from the Depots link you will find on the left hand side.
Here's an example - Take a look at this content depot taken from SteamDB for a Linux game (thanks to the developer of Rings of Saturn for allowing me to show their game as the example - they've fixed it since):
Now, compare that to the Windows version which clearly shows it having Store purchases and another additional package which the Linux version above did not:
The issue there, should be obvious. The Linux version needs setting up in the same way as the Windows version, being linked to all packages of keys and the Steam store purchase, otherwise we get the issue.
Note: I can't show the actual Steam developer area where you do it, since I am not a Steam developer and all that stuff Valve usually keep confidential. Valve have been emailed to confirm if we can show this.
However, in this video on the Steamworks Development YouTube channel, if you look at about 3:04 it shows the Configuring Depots section, that should be what you're after. Make sure the operating system dropdown box is set to the correct systems. Additionally, you can find this Steamworks Documentation page that explains some of it.
I see this multiple times per week, so hopefully this little tip will help a few developers.