Tanto quanto eu sei, não há versão "Samsung Kies" para o Ubuntu, mas o seguinte deve funcionar:
Conecte seu telefone à sua caixa via usb. No Ubuntu, vá até o miniaplicativo de rede e clique nele, clique em editar conexões, clique na guia Banda larga móvel, clique em adicionar. Seu telefone deve estar listado abaixo de "Criar uma conexão para este dispositivo de banda larga móvel". Clique em continuar, agora você precisa responder a várias perguntas sobre seu provedor e seu plano de faturamento. Você também pode precisar fornecer o nome do ponto de acesso. Você provavelmente não precisará alterar nada na nova janela de edição de conexão, basta salvar e testar sua nova conexão.