Se vc apenas escrever teste, o linux vai procurar o executável chamado teste em algumas pastas padrões do sistema (o /bin, /usr/bin, /usr/local/bin, etc).
Se seu programa está na pasta /home/fulano vc tem que usar o comando /home/fulano/teste pra executar o programa. Só que se vc já está no diretório /home/fulano você pode executar o programa apenas com ./teste
Isso ocorre porque o "." substitui o diretório atual. Logo ./teste vai ter o efeito de /home/fulano/teste
Por isso não dá pra tirar o "./"
Agora, quando vc inclui o diretório /home/fulano no PATH, o linux vai passar a olhar nessa pasta pra ver se acha um executável chamado "teste" quando vc tenta executar apenas "teste" no terminal. Aí a gente cai no primeiro caso e o seu programa vai funcionar sem o "./" (embora vc possa continuar a executálo com ./teste se quiser).