Passo 1: Encerre o seu computador agora (ou seja, pare de usar o sistema de arquivos que contém os arquivos excluídos).
Passo 2: Faça o download de uma imagem do Live CD em outro computador (o CD de Recuperação do Sistema seria uma boa escolha), queime-a em um CD-R, inicialize seu computador com ele e use as ferramentas de recuperação de dados disponíveis (por exemplo, photorec). Se os seus dados são realmente valiosos para você, considere clonar o disco antes de tentar qualquer recuperação de dados (você não quer piorar as coisas, não é?). Você pode usar partimage para isso (incluído no CD do System Rescue).
Etapa 3: não cometa o mesmo erro duas vezes: comece a fazer o backup de seus dados regularmente.