A solução é tão simples quanto adicionar os -l flags no end :
gcc test.c -o test -lssl -lcrypto
A ordem é importante porque ld desde o Ubuntu 11.04 é invocado com a opção -as-needed por padrão, para que os arquivos / bibliotecas que dependem de outras bibliotecas venham antes dessas outras bibliotecas, ou seja, test.c needs libcrypto , então deve vir antes de -lcrypto .
Para mais informações, veja Toolchain Transition em Natty Narwhal .