An 'executable' is either a valid ELF binary executable file or a properly formatted script for which the shell can find an interpreter. You can create an executable by writing (or downloading) a program in a compiled language (eg. usually C or C++) and then compiling it or you can create a script file in a scripting language such as bash, python, perl etc. that you have installed on your system. You usually need to set the executable permission on your executable file after you've compiled it or written it.
A program that executes in terminal mode is just one that doesn't have a GUI - you can create a shortcut ('Link to Application') to programs like this and in the options of the shortcut set to open them in a terminal. This means you can double click on the shortcut to run command line apps.