Evince (visualizador de PDF padrão) deve lembrar-se automaticamente das configurações de exibição individuais para documentos diferentes. No entanto, em 10.04, parece não haver uma preferência pelo modo de visualização padrão.
No Ubuntu 10.10 (GNOME 2.30), o Evince tem uma opção no menu Editar para isto: "Salvar as configurações atuais como padrão". Nesse caso, você alteraria o zoom para Melhor ajuste e configuraria todas as suas preferências de exibição e, em seguida, ativaria essa opção que se aplicaria a documentos futuros. Se você puder esperar um mês para que o 10.10 seja lançado e possa atualizar para isso, pode ser sua melhor aposta. Há outros visualizadores de PDFs por aí que já podem fazer isso, mas eu não achei tão simples de usar quanto o Evince.