Eu tive a mesma situação;
1-) Baixe o Ubuntu 14.04 e siga o guia de instalação do USB na web do Ubuntu
2-) Se o seu telefone tiver uma boa ROM, você não precisa de um apk para executar o tether, apenas conecte seu telefone no modo de depuração USB e o Ubuntu o reconhecerá como uma conexão a cabo. Mas se você precisar e apk eu sugiro Easytether, embora seja uma solução paga, funciona. Nota: se você baixar o Easytether Lite, você não poderá acessar qualquer https.//, você tem que comprar (se você quiser) o Easytether Pro.
O PdaNet não tem um aplicativo do lado do Cliente Linux, o modo ClockWork tem um aplicativo do Linux, mas é mais difícil de instalar, há também outros recursos como o Klink que eu não tentei.
Mas comparando com minha experiência no Windows com o PdaNet, devo dizer que a experiência de tethering no Ubuntu é ótima porque não é difícil de configurar e é mais automática (uma vez que você conecta as estrelas do telefone).