I have downloaded an add-on hosted on github today using this green 'Download/Clone' button. However, when I try to install it via User Preferences > Addons > Install it does not appear in the Add-on list, no matter what I do.

### Option 1 - Release version

If so, click on Releases Tab and download the latest release (zip or single py file):

There are lazy authors so in some rare cases the 'Clone or download' is the only option. Search for __init__.py in the repository and copy the folder containing this file to your Add-on directory:
• Linux: \$HOME/.config/blender/<version>/
• OSX: /Library/Application Support/Blender/<version>/
• Windows: %USERPROFILE%\AppData\Roaming\Blender Foundation\Blender\<version>\
You can get also get the folder per machine using the python console: bpy.utils.script_path_user() and / or bpy.utils.script_paths("addons")